Exhibit 5.1

[LETTERHEAD OF Cravath, Swaine & Moore LLP]

October 7, 2009

UAL Corporation

$345,000,000 Principal Amount of 6.0% Convertible Senior Notes due 2029 and

19,000,000 shares of Common Stock

Ladies and Gentlemen:

We have acted as counsel for UAL Corporation, a Delaware corporation (the “Company”), in connection with the public offering and sale by the Company of: (1) $345,000,000 aggregate principal amount of 6.0% Convertible Senior Notes due 2029 (the “Notes”) issued under an indenture dated as of October 7, 2009 (the “Indenture”), between the Company and The Bank of New York Mellon Trust Company, N.A., as trustee, and (2) 19,000,000 shares of common stock, par value $0.01 per share, of the Company (the “Common Stock”).

In that connection, we have examined originals, or copies certified or otherwise identified to our satisfaction, of such documents, corporate records, certificates of corporate officers and government officials and other instruments as we have deemed necessary or appropriate for the purposes of this opinion, including the Registration Statement on Form S-3 (Registration No. 333-155794), filed with the Securities and Exchange Commission (the “Commission”) on December 1, 2008, for registration under the Securities Act of 1933, as amended, of an indeterminate amount of debt securities and common stock to be issued from time to time by the Company (the “Registration Statement”).

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 and the authenticity of the originals of such latter documents. As to all documents 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 Company and documents furnished to us by the Company without independent verification of their accuracy.

Based upon and subject to the foregoing, we are of the opinion that:

1. The shares of Common Stock have been duly and validly authorized and, when issued and delivered by the Company, and paid for by the purchasers thereof, pursuant to the underwriting agreement, will be validly issued, fully paid and nonassessable; and

2. The Notes have been duly authorized and, when executed and authenticated with the provisions of the Indenture and delivered to and paid for the underwriters pursuant to the underwriting agreement, will constitute legal, valid and binding obligations of the Company, entitled to the benefits of the Indenture and enforceable against the Company in accordance with their terms (subject to applicable bankruptcy, insolvency, reorganization, moratorium, fraudulent transfer and other similar laws affecting creditors’ rights generally from time to time in effect and to general principles of equity, including, without limitations, concepts of materiality, reasonableness, good faith and fair dealing, regardless of whether considered in a proceeding in equity or at law).

We express no opinion herein as to any provision of the Indenture or the Notes that (a) relates to the subject matter jurisdiction of any Federal court of the United States of America, or any Federal appellate court, to adjudicate any controversy related to the Indenture or the Notes, (b) contains a waiver of an inconvenient forum or (c) relates to the waiver of rights to jury trial. We also express no opinion as to (i) the enforceability of the provisions of the Indenture or the Notes to the extent that such provisions constitute a waiver of illegality as a defense to performance of contract obligations or any other defense to performance which cannot, as a matter of law, be effectively waived or (ii) whether a state court outside the State of New York or a Federal court of the United States would give effect to the choice of New York law provided for in the Indenture or the Notes.

We hereby consent to the filing of this opinion with the Commission as an exhibit to the Registration Statement. We also consent to the reference to our firm under the caption “Legal Matters” in the Registration Statement. In giving this consent, we do not thereby admit that we are included in the category of persons whose consent is required under Section 7 of the Securities Act or the rules and regulations of the Commission.

2

We are admitted to practice in the State of New York, and we express no opinion as to matters governed by any laws other than the laws of the State of New York, the General Corporation Law and Limited Liability Company Act of the State of Delaware and the Federal laws of the United States of America.

UAL Corporation

77 West Wacker Drive

Chicago, IL 60601

O

3