Exhibit 5.1

Hughes Hubbard & Reed LLP

One Battery Park Plaza

New York, New York 10004

212-837-6000

April 27, 2012

United Continental Holdings, Inc.

77 W. Wacker Drive

Chicago, IL 60601

United Air Lines, Inc.

77 W. Wacker Drive

Chicago, IL 60601

Continental Airlines, Inc.

1600 Smith Street

Houston, Texas 77002

Re: Registration Statement on Form S-3

Ladies and Gentlemen:

We have acted as counsel for United Continental Holdings, Inc., a Delaware corporation (“UAL”), United Air Lines, Inc., a Delaware corporation (“United”), and Continental Airlines, Inc., a Delaware corporation (“Continental” and, together with UAL and United, the “Companies”), in connection with the filing by the Companies with the Securities and Exchange Commission (the “Commission”) of a registration statement (the “Registration Statement”) on Form S-3 under the Securities Act of 1933, as amended (the “Act”), relating to the registration under the Act of the proposed issuance and sale from time to time pursuant to Rule 415 under the Act of (a) common stock of UAL (the “Common Stock”), (b) debt securities of UAL in one or more series (the “UAL Debt Securities”) to be issued under an indenture among UAL, United, Continental and the trustee thereunder (the “Indenture Trustee”) in the form attached to the Registration Statement as Exhibit 4.1 (the “Indenture”), (c) debt securities of United in one or more series (the “United Debt Securities”) to be issued under the Indenture, (d) debt securities of Continental in one or more series (the “Continental Debt Securities” and, together with the UAL Debt Securities and the United Debt Securities, the “Debt Securities”) to be issued under the Indenture, (e) preferred stock of UAL (the “Preferred Stock”), (f) depositary shares of UAL (the “Depositary Shares”) representing a fractional interest in a share of Preferred Stock, (g) full and unconditional guarantees by UAL (the “UAL Debt Guarantees”) of the United

Debt Securities and the Continental Debt Securities to be issued under the Indenture, (h) full and unconditional guarantees by United (the “United Guarantees”) of the UAL Debt Securities and the Continental Debt Securities to be issued under the Indenture, (i) full and unconditional guarantees by Continental (the “Continental Guarantees” and, together with the UAL Debt Guarantees and the United Guarantees, the “Debt Guarantees”) of the UAL Debt Securities and the United Debt Securities to be issued under the Indenture, (j) contracts to purchase shares of Common Stock or other securities of UAL at a future date or dates (“Stock Purchase Contracts”), (k) stock purchase units of UAL consisting of a Stock Purchase Contract and UAL Debt Securities, Preferred Stock, Warrants (as defined below) or debt obligations of third parties (“Stock Purchase Units”), (l) subscription rights of UAL to purchase Common Stock, Preferred Stock, Depositary Shares or Warrants (“Subscription Rights”), (m) warrants of UAL to purchase UAL Debt Securities, Preferred Stock or Common Stock (the “Warrants” ), (n) pass through certificates (the “United Pass Through Certificates”) issued by one or more trusts (each, a “Trust”) to be formed by United, (o) pass through certificates (the “Continental Pass Through Certificates” and, together with the United Pass Through Certificates, the “Pass Through Certificates”) issued by one or more Trusts to be formed by Continental, (p) full and unconditional guarantees by UAL (the “UAL PTC Guarantees”) of certain obligations of United or Continental relating to property owned by a Trust that issues Pass Through Certificates, (q) full and unconditional guarantees by United (the “United PTC Guarantees”) of certain obligations of Continental relating to property owned by a Trust that issues Pass Through Certificates and (r) full and unconditional guarantees by Continental (the “Continental PTC Guarantees” and, together with the UAL PTC Guarantees and the United PTC Guarantees, the “PTC Guarantees”; and together with the other securities specified in clauses (a) through (q) above, the “Securities”) of certain obligations of United relating to property owned by a Trust that issues Pass Through Certificates.

The United Pass Through Certificates will be issued in one or more series under a Pass Through Trust Agreement (the “United Pass Through Trust Agreement”) between United and the trustee thereunder (the “United Trustee”) in the form filed as Exhibit 4.12 to the Registration Statement, and the Continental Pass Through Certificates will be issued in one or more series under a Pass Through Trust Agreement (together with the United Pass Through Trust Agreement, the “Basic Pass Through Trust Agreements”) between Continental and the trustee thereunder (together with the United Trustee, the “Trustees”), in the form filed as Exhibit 4.13 to the Registration Statement, in each case, as supplemented by a separate trust supplement (each, a “Trust Supplement”) relating to each such series.

We have examined, and have relied as to matters of fact upon, originals or copies, certified or otherwise identified to our satisfaction, of such corporate records, agreements, documents and other instruments and such certificates or comparable documents of public officials and of officers and representatives of each Company, and have made such other and further investigations as we have deemed relevant and necessary as a basis for the purposes of this opinion. In rendering our opinion, we have assumed the genuineness of all signatures, the legal capacity of all natural persons, the authenticity of all documents submitted to us as originals, the conformity to original documents of all documents submitted to us as certified, conformed or photostatic copies, the authenticity of the originals of such latter documents. As to all statements of fact material to this opinion that have not been independently established, we have relied upon certificates or comparable documents of officers and representatives of the Companies and documents furnished to us by the Companies without independent verification of their accuracy.

Page 2

The opinions set forth below that certain Securities constitute valid and binding obligations are subject to (i) limitations on enforceability arising from applicable bankruptcy, insolvency, reorganization, moratorium, receivership, fraudulent conveyance, fraudulent transfer, preferential transfer and similar laws relating to or affecting the rights and remedies of creditors generally and the effect of general principles of equity, including, without limitation, laches and estoppel as equitable defenses and concepts of materiality, reasonableness, good faith and fair dealing (regardless of whether such enforceability is considered or applied in a proceeding in equity or at law) and considerations of impracticability or impossibility of performance, and defenses based upon unconscionability of otherwise enforceable obligations in the context of the factual circumstances under which enforcement thereof is sought and (ii) the qualification that the remedy of specific performance and injunctive and other forms of equitable relief may be subject to equitable defenses and to the discretion of the court before which any proceeding therefor may be brought.

Based upon and subject to the foregoing, and assuming that: (i) the Registration Statement and any amendments thereto (including post-effective amendments) will be effective and will comply with all applicable laws at the time the Securities are offered or issued as contemplated by the Registration Statement; (ii) a prospectus supplement, pricing supplement or term sheet will have been prepared and filed with the Commission in compliance with the Act and the applicable rules and regulations thereunder describing the Securities offered thereby and will comply with all applicable laws (including the applicable provisions of such “blue sky” or state securities laws as may be applicable); (iii) at all relevant times UAL, United and Continental, as applicable, are validly existing corporations under the laws of the State of Delaware, and have the corporate power and authority to issue, execute and deliver the Securities, (iv) all Securities will be issued and sold in compliance with applicable federal and state securities laws and in the manner stated in the Registration Statement and the appropriate prospectus supplement; (v) none of the terms of any Security to be established subsequent to the date hereof, nor the issuance and delivery of such Security, nor the compliance by UAL, United or Continental, as applicable, with the terms of such Security will violate any applicable law, the certificate of incorporation or bylaws of UAL, United or Continental, as applicable, any provision of any instrument or agreement then binding upon UAL, United or Continental, as applicable, or any restriction imposed by any court or governmental body having jurisdiction over UAL, United or Continental, as applicable; (vi) a definitive purchase, underwriting or similar agreement with respect to any Securities offered or issued will have been duly authorized and validly executed and delivered by UAL, United or Continental, as applicable, and the other parties thereto and (vii) any Securities issuable upon conversion, exchange or exercise of any Security being offered or issued will be duly authorized, created and, if appropriate, reserved for issuance upon such conversion, exchange or exercise, we are of the opinion that:

(1) With respect to shares of Common Stock, when both (A) the board of directors or a duly constituted and acting committee thereof (such board of directors or committee being hereinafter referred to as the “Board”) of UAL has taken all necessary corporate action to approve the issuance of and the terms of the offering of the shares of Common Stock and related matters and (B) certificates in the form required under Delaware corporate law

Page 3

representing the shares of Common Stock have been duly executed, countersigned, registered and delivered either (i) in accordance with the applicable definitive purchase, underwriting or similar agreement approved by the Board of UAL against payment of the consideration therefor (not less than the par value of the Common Stock) provided for therein or (ii) upon conversion or exercise of any other Security, in accordance with the terms of such Security or the instrument governing such Security providing for such conversion or exercise as approved by the Board of UAL, against the consideration approved by the Board of UAL (not less than the par value of the Common Stock), then the shares of Common Stock will be legally issued, fully paid and nonassessable;

(2) With respect to the Debt Securities and the Debt Guarantees to be issued under the Indenture, when (A) the Indenture Trustee is qualified to act as the trustee under the Indenture, (B) the Indenture Trustee has duly executed and delivered the Indenture and any supplemental indenture thereunder, (C) the Indenture and any supplemental indenture thereunder have been duly authorized and validly executed and delivered to the Indenture Trustee by UAL, United and Continental, as applicable, (D) the Indenture has been duly qualified under the Trust Indenture Act of 1939, as amended, (E) the Board of UAL, United and Continental, as applicable, has taken all necessary corporate action to approve the issuance and terms of such Debt Securities and Debt Guarantees, if any, the terms of the offering thereof and related matters and (F) such Debt Securities and Debt Guarantees have been duly executed, authenticated, issued and delivered in accordance with the provisions of the Indenture, any supplemental indenture and the applicable definitive purchase, underwriting or similar agreement approved by the Board of UAL, United and Continental, as applicable, against payment of the consideration therefor provided for therein, such Debt Securities and Debt Guarantees will be legally issued and will constitute valid and binding obligations of UAL, United or Continental, as applicable;

(3) With respect to the Depositary Shares, when (A) the Board of UAL has taken all necessary corporate action to approve the issuance and terms of the Depositary Shares, the terms of the offering thereof, and related matters, including the adoption of a Certificate of Designations (a “Certificate”) relating to the Preferred Stock underlying such Depositary Shares and the filing of the Certificate with the Secretary of State of the State of Delaware, (B) the deposit agreement or agreements relating to the Depositary Shares and the related depositary receipts have been duly authorized and validly executed and delivered by UAL and the depositary appointed by UAL, (C) the shares of Preferred Stock underlying such Depositary Shares have been deposited with a bank or trust company (which meets the requirements for the Depositary set forth in the Registration Statement) under the applicable deposit agreement and (D) the depositary receipts representing the Depositary Shares have been duly executed, countersigned, registered and delivered in accordance with the appropriate deposit agreement and the applicable definitive purchase, underwriting or similar agreement approved by the Board of UAL against payment of the consideration therefor provided for therein, the Depositary Shares will be legally issued;

(4) With respect to shares of Preferred Stock, when both (A) the Board of UAL has taken all necessary corporate action to approve the issuance and terms of the shares of Preferred Stock, the terms of the offering thereof, and related matters, including the adoption of a Certificate and the filing of the Certificate with the Secretary of State of the State of Delaware and (B) certificates in the form required under Delaware corporate law representing the shares of

Page 4

Preferred Stock have been duly executed, countersigned, registered and delivered either (i) in accordance with the applicable definitive purchase, underwriting or similar agreement approved by the Board of UAL against payment of the consideration therefor (not less than the par value of the Preferred Stock) provided for therein or (ii) upon conversion or exercise of any other Security or the instrument governing such Security providing for such conversion or exercise as approved by the Board of UAL, for the consideration approved by the Board of UAL (not less than the par value of the Preferred Stock), then the shares of Preferred Stock will be legally issued, fully paid and nonassessable;

(5) With respect to Stock Purchase Contracts, when (i) the purchase agreement establishing the terms of the Stock Purchase Contracts has been duly authorized and validly executed by the parties thereto; (ii) the Board of UAL has taken all necessary corporate action to approve and establish the terms of the Stock Purchase Contracts and to authorize and approve the issuance thereof, the terms of the offering and related matters and (iii) the Stock Purchase Contracts have been duly executed and delivered in accordance with the purchase agreement and the applicable definitive purchase, underwriting or similar agreement approved by or on behalf of the Board of UAL against payment of the consideration therefor provided for therein, the Stock Purchase Contracts will be legally issued and will constitute valid and binding obligations of UAL;

(6) With respect to Stock Purchase Units, when (i) the purchase agreement establishing the terms of the Stock Purchase Units has been duly authorized and validly executed by the parties thereto, (ii) the Board of UAL has taken all necessary corporate action to approve and establish the terms of the Stock Purchase Units and to authorize and approve the issuance thereof, the terms of the offering and related matters and (iii) the Stock Purchase Units have been duly executed and delivered in accordance with the purchase agreement and the applicable definitive purchase, underwriting or similar agreement approved by or on behalf of the Board of UAL against payment of the consideration therefor provided therein, the Stock Purchase Units will be legally issued and will constitute valid and binding obligations of UAL;

(7) With respect to Subscription Rights, when (i) the Board of UAL has taken all necessary corporate action to approve the issuance and terms of the offering thereof and related matters and (ii) certificates representing the Subscription Rights have been duly executed, countersigned, registered and delivered by UAL, the Subscription Rights will be legally issued and will constitute valid and binding obligations of UAL;

(8) With respect to the Warrants, when (A) the Board of UAL has taken all necessary corporate action to approve the creation of and the issuance and terms of the Warrants, the terms of the offering thereof, and related matters, (B) the warrant agreement or agreements relating to the Warrants have been duly authorized and validly executed and delivered by UAL and the warrant agent appointed by UAL and (C) the Warrants or certificates representing the Warrants have been duly executed, countersigned, registered and delivered in accordance with the appropriate warrant agreement or agreements and the applicable definitive purchase, underwriting or similar agreement approved by the Board of UAL against payment of the consideration therefor provided for therein, the Warrants will be legally issued and will constitute valid and binding obligations of UAL;

Page 5

(9) With respect to each series of Pass Through Certificates and any related PTC Guarantees, when (A) the applicable Trustee is qualified to act as the trustee under the applicable Basic Pass Through Trust Agreement, (B) the applicable Trustee has duly executed and delivered the applicable Basic Pass Through Trust Agreement and Trust Supplement thereunder, (C) the applicable Basic Pass Through Trust Agreement, Trust Supplement thereunder and any applicable PTC Guarantee has been duly authorized and validly executed and delivered to the applicable Trustee by UAL, United or Continental, as applicable, (D) the applicable Basic Pass Through Trust Agreement has been duly qualified under the Trust Indenture Act of 1939, as amended, (E) the Board of UAL, United or Continental, as applicable, has taken all necessary corporate action to approve the issuance and terms of such Pass Through Certificates and PTC Guarantees, if any, the terms of the offering thereof and related matters and (F) such Pass Through Certificates and PTC Guarantees have been duly executed, authenticated, issued and delivered in accordance with the provisions of the applicable Basic Pass Through Trust Agreement, the applicable Trust Supplement and the applicable definitive purchase, underwriting or similar agreement approved by the Board of UAL, United and Continental, as applicable, against payment of the consideration therefor provided for therein, such Pass Through Certificates and PTC Guarantees will be legally issued and will constitute valid and binding obligations of the Trustee, in the case of the applicable Pass Through Certificates, or UAL, United or Continental, as applicable, in the case of any applicable PTC Guarantee.

We are members of the Bar of the State of New York, and we do not express any opinion herein concerning any law other than the law of the State of New York, the federal law of the United States and the Delaware General Corporation Law. We have assumed that each agreement constituting the Securities (other than Common Stock and Preferred Stock) will be governed by the laws of the State of New York.

We hereby consent to the filing of this opinion as an exhibit to the Registration Statement and we further consent to the use of our name under the caption “Legal Matters” in the forms of prospectus included in the Registration Statement. In giving this consent, we do not hereby admit that we are in the category of persons whose consent is required under Section 7 of the Act or the rules and regulations of the Commission thereunder.

Very truly yours,

/s/ Hughes Hubbard & Reed LLP