Exhibit 5.1

Sidley Austin LLP One South Dearborn Street Chicago, IL 60603 +1 312 853 7000 +1 312 853 7036 Fax AMERICA · ASIA PACIFIC · EUROPE

May 27, 2021

United Airlines Holdings, Inc.

233 South Wacker Drive

Chicago, IL 60606

Re: Post-Effective Amendment No. 1 to Registration Statement on Form S-8

Ladies and Gentlemen:

We refer to the Post-Effective Amendment No. 1 (the “Post-Effective Amendment”) to Registration Statement No. 333-218637 on Form S-8 (the “Registration Statement”) being filed by United Airlines Holdings, Inc., a Delaware corporation (the “Company”), with the Securities and Exchange Commission under the Securities Act of 1933, as amended (the “Securities Act”), covering shares of Common Stock, $0.01 par value per share, of the Company (“Common Stock”) and Series A Junior Participating Serial Preferred Stock Purchase Rights (the “Rights”) associated therewith, which may be issued under the United Airlines Holdings, Inc. 2021 Incentive Compensation Plan (the “2021 Plan”). The terms of the Rights are set forth in the Tax Benefits Preservation Plan, dated as of December 4, 2020, as amended January 21, 2021 (the “Rights Agreement”), by and between the Company and Computershare Trust Company, N.A., as Rights Agent.

On May 26, 2021 (the “Effective Date”), the stockholders of the Company approved the 2021 Plan. The total number of shares of Common Stock that may be granted under the 2021 Plan includes, in addition to 3,600,000 new shares of Common Stock, together with the Rights associated therewith (included by the Company on a new Registration Statement on Form S-8 filed on May 27, 2021), (i) the number of shares that remained available for issuance under the United Continental Holdings, Inc. 2017 Incentive Compensation Plan (the “2017 Plan”) as of the Effective Date and (ii) the undelivered shares subject to outstanding awards granted under the 2017 Plan that become available for future awards under the 2021 Plan as provided for in the 2021 Plan (the shares described in (i) and (ii), the “2017 Plan Shares”).

This opinion letter is being delivered in accordance with the requirements of Item 601(b)(5) of Regulation S-K under the Securities Act.

Sidley Austin LLP is a limited liability partnership practicing in affiliation with other Sidley Austin partnerships.

United Airlines Holdings, Inc.

May 27, 2021

Page 2

We have examined the Post-Effective Amendment, the Registration Statement, the Company’s Amended and Restated Certificate of Incorporation, the Company’s Amended and Restated Bylaws, the Rights Agreement, the 2021 Plan, the resolutions adopted by the board of directors of the Company (the “Board”) relating to the Registration Statement and the 2021 Plan and the proposal adopted by the stockholders of the Company relating to the 2021 Plan at the Company’s 2021 Annual Meeting of Stockholders. We have also examined originals, or copies of originals certified to our satisfaction, of such agreements, documents, certificates and statements of the Company and other corporate documents and instruments, and have examined such questions of law, as we have considered relevant and necessary as a basis for this opinion letter. We have assumed the authenticity of all documents submitted to us as originals, the genuineness of all signatures, the legal capacity of all persons and the conformity with the original documents of any copies thereof submitted to us for examination. As to facts relevant to the opinions expressed herein, we have relied without independent investigation or verification upon, and assumed the accuracy and completeness of, certificates, letters and oral and written statements and representations of public officials and officers and other representatives of the Company.

Based on the foregoing, we are of the opinion that:

1.            Each 2017 Plan Share that is newly issued pursuant to the 2021 Plan will be validly issued, fully paid and non-assessable when: (i) the Post-Effective Amendment shall have become effective under the Securities Act; (ii) such 2017 Plan Share shall have been duly issued and delivered in accordance with the 2021 Plan; and (iii) certificates representing such 2017 Plan Share shall have been duly executed, countersigned and registered and duly delivered to the person entitled thereto against payment of the agreed consideration therefor (in an amount not less than the par value thereof) or, if any 2017 Plan Share is to be issued in uncertificated form, the Company’s books shall reflect the issuance of such 2017 Plan Share to the person entitled thereto against payment of the agreed consideration therefor (in an amount not less than the par value thereof), all in accordance with the 2021 Plan.

2.            The Right associated with each 2017 Plan Share will be validly issued, fully paid and non-assessable when (i) the Post-Effective Amendment, as finally amended, shall have been declared effective under the Securities Act; (ii) such associated 2017 Plan Share shall have been duly issued as set forth in paragraph 1 above; and (iii) such Right shall have been duly issued in accordance with the terms of the Rights Agreement.

In rendering the opinion in paragraph 2 above, we have also assumed that the Rights Agreement has been duly authorized, executed and delivered by the Rights Agent and that the members of the Board have acted in a manner consistent with their fiduciary duties as required under applicable law in adopting the Rights Agreement. Such opinion does not address the determination a court of competent jurisdiction may make regarding whether the Board may be required to redeem or terminate, or take other action with respect to, the Rights in the future based on the facts and circumstances then existing. Such opinion addresses corporate procedures in connection with the issuance of the Rights associated with the 2017 Plan Share, and not any particular provision of the Rights or the Rights Agreement. We note that it is not settled whether the invalidity of any particular provision of a rights agreement or purchase rights issued thereunder would invalidate such rights in their entirety.

United Airlines Holdings, Inc.

May 27, 2021

Page 3

This opinion letter is limited to the General Corporation Law of the State of Delaware. We express no opinion as to the laws, rules or regulations of any other jurisdiction, including, without limitation, the federal laws of the United States of America or any state securities or blue sky laws.

We hereby consent to the filing of this opinion letter as an Exhibit to the Registration Statement and to all references to our Firm included in or made a part of the Registration Statement. In giving such consent, we do not thereby admit that we are in the category of persons whose consent is required under Section 7 of the Securities Act.

Very truly yours,

/s/ Sidley Austin LLP

Sidley Austin LLP