<?xml version="1.0" encoding="US-ASCII"?>
<!--XBRL Document Created with Wdesk from Workiva-->
<!-- -->
<link:linkbase xsi:schemaLocation="http://www.xbrl.org/2003/linkbase http://www.xbrl.org/2003/xbrl-linkbase-2003-12-31.xsd" xmlns:link="http://www.xbrl.org/2003/linkbase" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance">
  <link:roleRef roleURI="http://www.unitedcontinentalholdings.com/role/DocumentAndEntityInformation" xlink:href="ual-20200720.xsd#DocumentAndEntityInformation" xlink:type="simple" />
  <link:roleRef roleURI="http://www.xbrl.org/2009/role/negatedLabel" xlink:href="http://www.xbrl.org/lrr/role/negated-2009-12-16.xsd#negatedLabel" xlink:type="simple" />
  <link:roleRef roleURI="http://www.xbrl.org/2009/role/negatedNetLabel" xlink:href="http://www.xbrl.org/lrr/role/negated-2009-12-16.xsd#negatedNetLabel" xlink:type="simple" />
  <link:roleRef roleURI="http://www.xbrl.org/2009/role/negatedPeriodEndLabel" xlink:href="http://www.xbrl.org/lrr/role/negated-2009-12-16.xsd#negatedPeriodEndLabel" xlink:type="simple" />
  <link:roleRef roleURI="http://www.xbrl.org/2009/role/negatedPeriodStartLabel" xlink:href="http://www.xbrl.org/lrr/role/negated-2009-12-16.xsd#negatedPeriodStartLabel" xlink:type="simple" />
  <link:roleRef roleURI="http://www.xbrl.org/2009/role/negatedTerseLabel" xlink:href="http://www.xbrl.org/lrr/role/negated-2009-12-16.xsd#negatedTerseLabel" xlink:type="simple" />
  <link:roleRef roleURI="http://www.xbrl.org/2009/role/negatedTotalLabel" xlink:href="http://www.xbrl.org/lrr/role/negated-2009-12-16.xsd#negatedTotalLabel" xlink:type="simple" />
  <link:roleRef roleURI="http://www.xbrl.org/2009/role/netLabel" xlink:href="http://www.xbrl.org/lrr/role/net-2009-12-16.xsd#netLabel" xlink:type="simple" />
  <link:presentationLink xlink:role="http://www.unitedcontinentalholdings.com/role/DocumentAndEntityInformation" xlink:type="extended">
    <link:loc xlink:href="https://xbrl.sec.gov/dei/2019/dei-2019-01-31.xsd#dei_CoverAbstract" xlink:label="loc_dei_CoverAbstract_8A6A88ADE1D94C67DB2370B689F3D3E6" xlink:type="locator" />
    <link:loc xlink:href="https://xbrl.sec.gov/dei/2019/dei-2019-01-31.xsd#dei_EntitiesTable" xlink:label="loc_dei_EntitiesTable_EB9CD2EB0A67CFA94A1670B689F31A36" xlink:type="locator" />
    <link:presentationArc order="1" preferredLabel="http://www.xbrl.org/2003/role/terseLabel" xlink:arcrole="http://www.xbrl.org/2003/arcrole/parent-child" xlink:from="loc_dei_CoverAbstract_8A6A88ADE1D94C67DB2370B689F3D3E6" xlink:to="loc_dei_EntitiesTable_EB9CD2EB0A67CFA94A1670B689F31A36" xlink:type="arc" />
    <link:loc xlink:href="https://xbrl.sec.gov/dei/2019/dei-2019-01-31.xsd#dei_LegalEntityAxis" xlink:label="loc_dei_LegalEntityAxis_26A126EA1F2650CCF26E70B689F396AC" xlink:type="locator" />
    <link:presentationArc order="1" preferredLabel="http://www.xbrl.org/2003/role/terseLabel" xlink:arcrole="http://www.xbrl.org/2003/arcrole/parent-child" xlink:from="loc_dei_EntitiesTable_EB9CD2EB0A67CFA94A1670B689F31A36" xlink:to="loc_dei_LegalEntityAxis_26A126EA1F2650CCF26E70B689F396AC" xlink:type="arc" />
    <link:loc xlink:href="https://xbrl.sec.gov/dei/2019/dei-2019-01-31.xsd#dei_EntityDomain" xlink:label="loc_dei_EntityDomain_8E2205FD5955AB65DA7970B689F398C7" xlink:type="locator" />
    <link:presentationArc order="1" preferredLabel="http://www.xbrl.org/2003/role/terseLabel" xlink:arcrole="http://www.xbrl.org/2003/arcrole/parent-child" xlink:from="loc_dei_LegalEntityAxis_26A126EA1F2650CCF26E70B689F396AC" xlink:to="loc_dei_EntityDomain_8E2205FD5955AB65DA7970B689F398C7" xlink:type="arc" />
    <link:loc xlink:href="ual-20200720.xsd#ual_UnitedAirLinesIncMember" xlink:label="loc_ual_UnitedAirLinesIncMember_61BD4D256E14A2CBB8C470B689FD635D" xlink:type="locator" />
    <link:presentationArc order="1" preferredLabel="http://www.xbrl.org/2003/role/terseLabel" xlink:arcrole="http://www.xbrl.org/2003/arcrole/parent-child" xlink:from="loc_dei_EntityDomain_8E2205FD5955AB65DA7970B689F398C7" xlink:to="loc_ual_UnitedAirLinesIncMember_61BD4D256E14A2CBB8C470B689FD635D" xlink:type="arc" />
    <link:loc xlink:href="https://xbrl.sec.gov/dei/2019/dei-2019-01-31.xsd#dei_EntityInformationLineItems" xlink:label="loc_dei_EntityInformationLineItems_AC61D885DBC579DBDBD870B689FDC84B" xlink:type="locator" />
    <link:presentationArc order="2" preferredLabel="http://www.xbrl.org/2003/role/terseLabel" xlink:arcrole="http://www.xbrl.org/2003/arcrole/parent-child" xlink:from="loc_dei_EntitiesTable_EB9CD2EB0A67CFA94A1670B689F31A36" xlink:to="loc_dei_EntityInformationLineItems_AC61D885DBC579DBDBD870B689FDC84B" xlink:type="arc" />
    <link:loc xlink:href="https://xbrl.sec.gov/dei/2019/dei-2019-01-31.xsd#dei_DocumentType" xlink:label="loc_dei_DocumentType_4B363B7D6B3FD1ECE40770B689FD607B" xlink:type="locator" />
    <link:presentationArc order="1" preferredLabel="http://www.xbrl.org/2003/role/terseLabel" xlink:arcrole="http://www.xbrl.org/2003/arcrole/parent-child" xlink:from="loc_dei_EntityInformationLineItems_AC61D885DBC579DBDBD870B689FDC84B" xlink:to="loc_dei_DocumentType_4B363B7D6B3FD1ECE40770B689FD607B" xlink:type="arc" />
    <link:loc xlink:href="https://xbrl.sec.gov/dei/2019/dei-2019-01-31.xsd#dei_AmendmentFlag" xlink:label="loc_dei_AmendmentFlag_9D8D2DF8B4F81626BBAF70B689FD67F6" xlink:type="locator" />
    <link:presentationArc order="2" preferredLabel="http://www.xbrl.org/2003/role/terseLabel" xlink:arcrole="http://www.xbrl.org/2003/arcrole/parent-child" xlink:from="loc_dei_EntityInformationLineItems_AC61D885DBC579DBDBD870B689FDC84B" xlink:to="loc_dei_AmendmentFlag_9D8D2DF8B4F81626BBAF70B689FD67F6" xlink:type="arc" />
    <link:loc xlink:href="https://xbrl.sec.gov/dei/2019/dei-2019-01-31.xsd#dei_DocumentPeriodEndDate" xlink:label="loc_dei_DocumentPeriodEndDate_BD11130CA19BCCF4B2EA70B689FD30D4" xlink:type="locator" />
    <link:presentationArc order="3" preferredLabel="http://www.xbrl.org/2003/role/terseLabel" xlink:arcrole="http://www.xbrl.org/2003/arcrole/parent-child" xlink:from="loc_dei_EntityInformationLineItems_AC61D885DBC579DBDBD870B689FDC84B" xlink:to="loc_dei_DocumentPeriodEndDate_BD11130CA19BCCF4B2EA70B689FD30D4" xlink:type="arc" />
    <link:loc xlink:href="https://xbrl.sec.gov/dei/2019/dei-2019-01-31.xsd#dei_EntityRegistrantName" xlink:label="loc_dei_EntityRegistrantName_BF981C7C7507F643A72D70B689FD149D" xlink:type="locator" />
    <link:presentationArc order="4" preferredLabel="http://www.xbrl.org/2003/role/terseLabel" xlink:arcrole="http://www.xbrl.org/2003/arcrole/parent-child" xlink:from="loc_dei_EntityInformationLineItems_AC61D885DBC579DBDBD870B689FDC84B" xlink:to="loc_dei_EntityRegistrantName_BF981C7C7507F643A72D70B689FD149D" xlink:type="arc" />
    <link:loc xlink:href="https://xbrl.sec.gov/dei/2019/dei-2019-01-31.xsd#dei_EntityCentralIndexKey" xlink:label="loc_dei_EntityCentralIndexKey_92AA9873D4DB31D85C8070B689FDFE2C" xlink:type="locator" />
    <link:presentationArc order="5" preferredLabel="http://www.xbrl.org/2003/role/terseLabel" xlink:arcrole="http://www.xbrl.org/2003/arcrole/parent-child" xlink:from="loc_dei_EntityInformationLineItems_AC61D885DBC579DBDBD870B689FDC84B" xlink:to="loc_dei_EntityCentralIndexKey_92AA9873D4DB31D85C8070B689FDFE2C" xlink:type="arc" />
    <link:loc xlink:href="https://xbrl.sec.gov/dei/2019/dei-2019-01-31.xsd#dei_EntityIncorporationStateCountryCode" xlink:label="loc_dei_EntityIncorporationStateCountryCode_21472FF4F5A230AC48C470B689FD6187" xlink:type="locator" />
    <link:presentationArc order="6" preferredLabel="http://www.xbrl.org/2003/role/terseLabel" xlink:arcrole="http://www.xbrl.org/2003/arcrole/parent-child" xlink:from="loc_dei_EntityInformationLineItems_AC61D885DBC579DBDBD870B689FDC84B" xlink:to="loc_dei_EntityIncorporationStateCountryCode_21472FF4F5A230AC48C470B689FD6187" xlink:type="arc" />
    <link:loc xlink:href="https://xbrl.sec.gov/dei/2019/dei-2019-01-31.xsd#dei_EntityFileNumber" xlink:label="loc_dei_EntityFileNumber_A6E71B8848C53DEC4F6670B689FD6F05" xlink:type="locator" />
    <link:presentationArc order="7" preferredLabel="http://www.xbrl.org/2003/role/terseLabel" xlink:arcrole="http://www.xbrl.org/2003/arcrole/parent-child" xlink:from="loc_dei_EntityInformationLineItems_AC61D885DBC579DBDBD870B689FDC84B" xlink:to="loc_dei_EntityFileNumber_A6E71B8848C53DEC4F6670B689FD6F05" xlink:type="arc" />
    <link:loc xlink:href="https://xbrl.sec.gov/dei/2019/dei-2019-01-31.xsd#dei_EntityTaxIdentificationNumber" xlink:label="loc_dei_EntityTaxIdentificationNumber_D2EA71CFC0907F633F0F70B689FD87F1" xlink:type="locator" />
    <link:presentationArc order="8" preferredLabel="http://www.xbrl.org/2003/role/terseLabel" xlink:arcrole="http://www.xbrl.org/2003/arcrole/parent-child" xlink:from="loc_dei_EntityInformationLineItems_AC61D885DBC579DBDBD870B689FDC84B" xlink:to="loc_dei_EntityTaxIdentificationNumber_D2EA71CFC0907F633F0F70B689FD87F1" xlink:type="arc" />
    <link:loc xlink:href="https://xbrl.sec.gov/dei/2019/dei-2019-01-31.xsd#dei_EntityAddressAddressLine1" xlink:label="loc_dei_EntityAddressAddressLine1_BAC09FDC95DB2948E9A170B689FD80EF" xlink:type="locator" />
    <link:presentationArc order="9" preferredLabel="http://www.xbrl.org/2003/role/terseLabel" xlink:arcrole="http://www.xbrl.org/2003/arcrole/parent-child" xlink:from="loc_dei_EntityInformationLineItems_AC61D885DBC579DBDBD870B689FDC84B" xlink:to="loc_dei_EntityAddressAddressLine1_BAC09FDC95DB2948E9A170B689FD80EF" xlink:type="arc" />
    <link:loc xlink:href="https://xbrl.sec.gov/dei/2019/dei-2019-01-31.xsd#dei_EntityAddressCityOrTown" xlink:label="loc_dei_EntityAddressCityOrTown_C85C2B426C14C2F3715E70B689FDCD16" xlink:type="locator" />
    <link:presentationArc order="10" preferredLabel="http://www.xbrl.org/2003/role/terseLabel" xlink:arcrole="http://www.xbrl.org/2003/arcrole/parent-child" xlink:from="loc_dei_EntityInformationLineItems_AC61D885DBC579DBDBD870B689FDC84B" xlink:to="loc_dei_EntityAddressCityOrTown_C85C2B426C14C2F3715E70B689FDCD16" xlink:type="arc" />
    <link:loc xlink:href="https://xbrl.sec.gov/dei/2019/dei-2019-01-31.xsd#dei_EntityAddressStateOrProvince" xlink:label="loc_dei_EntityAddressStateOrProvince_C738DCA2EFFBF3CA477E70B689FD0316" xlink:type="locator" />
    <link:presentationArc order="11" preferredLabel="http://www.xbrl.org/2003/role/terseLabel" xlink:arcrole="http://www.xbrl.org/2003/arcrole/parent-child" xlink:from="loc_dei_EntityInformationLineItems_AC61D885DBC579DBDBD870B689FDC84B" xlink:to="loc_dei_EntityAddressStateOrProvince_C738DCA2EFFBF3CA477E70B689FD0316" xlink:type="arc" />
    <link:loc xlink:href="https://xbrl.sec.gov/dei/2019/dei-2019-01-31.xsd#dei_EntityAddressPostalZipCode" xlink:label="loc_dei_EntityAddressPostalZipCode_F61B78F73C9E059DD9AA70B689FDEC2F" xlink:type="locator" />
    <link:presentationArc order="12" preferredLabel="http://www.xbrl.org/2003/role/terseLabel" xlink:arcrole="http://www.xbrl.org/2003/arcrole/parent-child" xlink:from="loc_dei_EntityInformationLineItems_AC61D885DBC579DBDBD870B689FDC84B" xlink:to="loc_dei_EntityAddressPostalZipCode_F61B78F73C9E059DD9AA70B689FDEC2F" xlink:type="arc" />
    <link:loc xlink:href="https://xbrl.sec.gov/dei/2019/dei-2019-01-31.xsd#dei_CityAreaCode" xlink:label="loc_dei_CityAreaCode_73158E6FEB4EA2423A7B70B689FD87A5" xlink:type="locator" />
    <link:presentationArc order="13" preferredLabel="http://www.xbrl.org/2003/role/terseLabel" xlink:arcrole="http://www.xbrl.org/2003/arcrole/parent-child" xlink:from="loc_dei_EntityInformationLineItems_AC61D885DBC579DBDBD870B689FDC84B" xlink:to="loc_dei_CityAreaCode_73158E6FEB4EA2423A7B70B689FD87A5" xlink:type="arc" />
    <link:loc xlink:href="https://xbrl.sec.gov/dei/2019/dei-2019-01-31.xsd#dei_LocalPhoneNumber" xlink:label="loc_dei_LocalPhoneNumber_86166E76AA726661EE5670B689FD5FD6" xlink:type="locator" />
    <link:presentationArc order="14" preferredLabel="http://www.xbrl.org/2003/role/terseLabel" xlink:arcrole="http://www.xbrl.org/2003/arcrole/parent-child" xlink:from="loc_dei_EntityInformationLineItems_AC61D885DBC579DBDBD870B689FDC84B" xlink:to="loc_dei_LocalPhoneNumber_86166E76AA726661EE5670B689FD5FD6" xlink:type="arc" />
    <link:loc xlink:href="https://xbrl.sec.gov/dei/2019/dei-2019-01-31.xsd#dei_WrittenCommunications" xlink:label="loc_dei_WrittenCommunications_55BFA7A756E101A2AEFA70B689FD2F11" xlink:type="locator" />
    <link:presentationArc order="15" preferredLabel="http://www.xbrl.org/2003/role/terseLabel" xlink:arcrole="http://www.xbrl.org/2003/arcrole/parent-child" xlink:from="loc_dei_EntityInformationLineItems_AC61D885DBC579DBDBD870B689FDC84B" xlink:to="loc_dei_WrittenCommunications_55BFA7A756E101A2AEFA70B689FD2F11" xlink:type="arc" />
    <link:loc xlink:href="https://xbrl.sec.gov/dei/2019/dei-2019-01-31.xsd#dei_SolicitingMaterial" xlink:label="loc_dei_SolicitingMaterial_DC97A5EB21FB7CD9993B70B689FD65F5" xlink:type="locator" />
    <link:presentationArc order="16" preferredLabel="http://www.xbrl.org/2003/role/terseLabel" xlink:arcrole="http://www.xbrl.org/2003/arcrole/parent-child" xlink:from="loc_dei_EntityInformationLineItems_AC61D885DBC579DBDBD870B689FDC84B" xlink:to="loc_dei_SolicitingMaterial_DC97A5EB21FB7CD9993B70B689FD65F5" xlink:type="arc" />
    <link:loc xlink:href="https://xbrl.sec.gov/dei/2019/dei-2019-01-31.xsd#dei_PreCommencementTenderOffer" xlink:label="loc_dei_PreCommencementTenderOffer_CF16CA4B3DE37F8FC6D470B689FD710E" xlink:type="locator" />
    <link:presentationArc order="17" preferredLabel="http://www.xbrl.org/2003/role/terseLabel" xlink:arcrole="http://www.xbrl.org/2003/arcrole/parent-child" xlink:from="loc_dei_EntityInformationLineItems_AC61D885DBC579DBDBD870B689FDC84B" xlink:to="loc_dei_PreCommencementTenderOffer_CF16CA4B3DE37F8FC6D470B689FD710E" xlink:type="arc" />
    <link:loc xlink:href="https://xbrl.sec.gov/dei/2019/dei-2019-01-31.xsd#dei_PreCommencementIssuerTenderOffer" xlink:label="loc_dei_PreCommencementIssuerTenderOffer_8B4829E9919B06836F3070B689FDCA83" xlink:type="locator" />
    <link:presentationArc order="18" preferredLabel="http://www.xbrl.org/2003/role/terseLabel" xlink:arcrole="http://www.xbrl.org/2003/arcrole/parent-child" xlink:from="loc_dei_EntityInformationLineItems_AC61D885DBC579DBDBD870B689FDC84B" xlink:to="loc_dei_PreCommencementIssuerTenderOffer_8B4829E9919B06836F3070B689FDCA83" xlink:type="arc" />
    <link:loc xlink:href="https://xbrl.sec.gov/dei/2019/dei-2019-01-31.xsd#dei_Security12bTitle" xlink:label="loc_dei_Security12bTitle_9A4142A19C8A0DB7A3C770B689FD9D9E" xlink:type="locator" />
    <link:presentationArc order="19" preferredLabel="http://www.xbrl.org/2003/role/terseLabel" xlink:arcrole="http://www.xbrl.org/2003/arcrole/parent-child" xlink:from="loc_dei_EntityInformationLineItems_AC61D885DBC579DBDBD870B689FDC84B" xlink:to="loc_dei_Security12bTitle_9A4142A19C8A0DB7A3C770B689FD9D9E" xlink:type="arc" />
    <link:loc xlink:href="https://xbrl.sec.gov/dei/2019/dei-2019-01-31.xsd#dei_TradingSymbol" xlink:label="loc_dei_TradingSymbol_E20817ACC8C64B1EB7B770B689FD9615" xlink:type="locator" />
    <link:presentationArc order="20" preferredLabel="http://www.xbrl.org/2003/role/terseLabel" xlink:arcrole="http://www.xbrl.org/2003/arcrole/parent-child" xlink:from="loc_dei_EntityInformationLineItems_AC61D885DBC579DBDBD870B689FDC84B" xlink:to="loc_dei_TradingSymbol_E20817ACC8C64B1EB7B770B689FD9615" xlink:type="arc" />
    <link:loc xlink:href="https://xbrl.sec.gov/dei/2019/dei-2019-01-31.xsd#dei_SecurityExchangeName" xlink:label="loc_dei_SecurityExchangeName_65B8467E5895F89D3FDD70B689FDB215" xlink:type="locator" />
    <link:presentationArc order="21" preferredLabel="http://www.xbrl.org/2003/role/terseLabel" xlink:arcrole="http://www.xbrl.org/2003/arcrole/parent-child" xlink:from="loc_dei_EntityInformationLineItems_AC61D885DBC579DBDBD870B689FDC84B" xlink:to="loc_dei_SecurityExchangeName_65B8467E5895F89D3FDD70B689FDB215" xlink:type="arc" />
    <link:loc xlink:href="https://xbrl.sec.gov/dei/2019/dei-2019-01-31.xsd#dei_EntityEmergingGrowthCompany" xlink:label="loc_dei_EntityEmergingGrowthCompany_50ABC020BC37A4B460EB70B689FD6730" xlink:type="locator" />
    <link:presentationArc order="22" preferredLabel="http://www.xbrl.org/2003/role/terseLabel" xlink:arcrole="http://www.xbrl.org/2003/arcrole/parent-child" xlink:from="loc_dei_EntityInformationLineItems_AC61D885DBC579DBDBD870B689FDC84B" xlink:to="loc_dei_EntityEmergingGrowthCompany_50ABC020BC37A4B460EB70B689FD6730" xlink:type="arc" />
  </link:presentationLink>
</link:linkbase>
