Exhibit 3.1

AMENDED AND RESTATED

CERTIFICATE OF INCORPORATION

ARTICLE I

The name of the corporation (hereinafter called the “Corporation”) is UNITED AIRLINES, INC.

ARTICLE II

The address of the Corporation’s registered office in the State of Delaware is 1209 Orange Street, Wilmington, New Castle County 19801. The name of the Corporation’s registered agent at such address is The Corporation Trust Company.

ARTICLE III

The purpose of the Corporation is to engage in any lawful act or activity for which corporations may be organized under the General Corporation Law of the State of Delaware (the “DGCL”).

ARTICLE IV

The total number of shares of all classes of stock that the Corporation shall have authority to issue is 1,000 shares of Common Stock having the par value of $0.01 per share.

ARTICLE V

The number of directors of the Corporation shall be fixed from time to time by the Board of Directors of the Corporation.

ARTICLE VI

In furtherance and not in limitation of the powers conferred upon it by law, the Board of Directors of the Corporation is expressly authorized to adopt, amend or repeal the By-laws of the Corporation.

ARTICLE VII

Unless and except to the extent that the DGCL or By-laws of the Corporation so require, the election of directors of the Corporation need not be by written ballot.

ARTICLE VIII

(a) A director of the Corporation shall not be personally liable to the Corporation or its stockholders for monetary damages for breach of fiduciary duty as a director, except for liability (i) for any breach of the director’s duty of loyalty to the Corporation or its stockholders, (ii) for acts or omissions not in good faith or which involve intentional misconduct or a knowing violation of law, (iii) under Section 174 of the DGCL, or (iv) for any transaction from which the director derived an improper personal benefit. If the DGCL is amended to authorize corporate action further eliminating or limiting the personal liability of directors, then the liability of a director of the Corporation shall be eliminated or limited to the fullest extent permitted by the DGCL, as so amended.

(b) Each person who was or is made a party or is threatened to be made a party or is involved in any threatened, pending or completed action, suit or proceeding, whether civil, criminal, administrative or investigative (hereinafter a “proceeding”), by reason of the fact that he or she, or a person of whom he or she is the legal representative, is or was a director or officer of the Corporation or is or was serving at the request of the Corporation as a director, officer or employee of another corporation or of a partnership, joint venture, trust or other enterprise, including service with respect to employee benefit plans, whether the basis of such proceeding is alleged action in an official capacity as a director or officer or in any other capacity while serving as a director, officer or employee shall be indemnified and held harmless by the Corporation to the fullest extent authorized by the DGCL, as the same exists or may hereafter be amended (but, in the case of any such amendment, only to the extent that such amendment permits the Corporation to provide broader indemnification rights than said law permitted the Corporation to provide prior to such amendment), against all expense, liability and loss (including attorneys’ fees, judgments, fines, ERISA excise taxes or penalties and amounts paid or to be paid in settlement) actually and reasonably incurred or suffered by such person in connection therewith. Such indemnification shall continue as to a person who has ceased to be a director or officer and shall inure to the benefit of his or her heirs, executors and administrators; provided, however, that, except as provided in paragraph (c) of this Article VIII, the Corporation shall indemnify any such person seeking indemnification in connection with a proceeding (or part thereof) initiated by such person only if such proceeding (or part thereof) was authorized by the Board of Directors. Notwithstanding anything to the contrary herein, the Corporation shall not be obligated to indemnify a director or officer for costs and expenses relating to proceedings (or any part thereof) instituted against the Corporation by such director or officer (other than proceedings pursuant to which such director or officer is seeking to enforce such director’s or officer’s indemnification rights hereunder). The right to indemnification conferred in this Article VIII with respect to directors and officers shall be a contract right and shall include the right to be paid by the Corporation the expenses incurred in defending any such proceeding in advance of its final disposition; provided, however, that, if the DGCL requires, the payment of such expense incurred by a director or officer in his or her capacity as a director or officer (and not in any other capacity in which service was or is rendered by such person while a director or officer, including, without limitation, service to an employee benefit plan) in advance of the final disposition of a proceeding, shall be made only upon delivery to the Corporation of an undertaking, by or on behalf of such director or officer, to repay all amounts so advanced if it shall ultimately be determined that such director or officer is not entitled to be indemnified under this Article VIII or otherwise. The Corporation may provide indemnification to employees (other than officers) and agents of the Corporation with the same scope and effect as the foregoing indemnification of directors and officers to the extent (i) permitted by the laws of the State of Delaware as from time to time in effect, and (ii) authorized in the sole discretion of any of the Chief Executive Officer, the President, the Chief Financial Officer or the General Counsel of the Corporation; provided, however, that any such indemnification shall not constitute a contract right for any such employee or agent.

2

(c) If a claim under paragraph (b) or this Article VIII is not paid in full by the Corporation within thirty days after a written claim has been received by the Corporation, the claimant may at any time thereafter bring suit against the Corporation to recover the unpaid amount of the claim and, if successful in whole or in part, the claimant shall be entitled to be paid also the expense of prosecuting such claim. It shall be a defense to any such action (other than an action brought to enforce a claim for expenses incurred in defending any proceeding in advance of its final disposition where the required undertaking, if any is required, has been tendered to the Corporation) that the claimant has not met the standards of conduct which make it permissible under the DGCL for the Corporation to indemnify the claimant for the amount claimed, but the burden of proving such defense shall be on the Corporation. Neither the failure of the Corporation (including its Board of Directors, independent legal counsel, or its stockholders) to have made a determination prior to the commencement of such action that indemnification of the claimant is proper in the circumstances because he or she has met the applicable standard of conducts set forth in the DGCL, nor an actual determination by the Corporation (including its Board of Directors, independent legal counsel, or its stockholders) that the claimant has not met such applicable standard of conduct, shall be a defense to the action or create a presumption that the claimant has not met the applicable standard of conduct.

(d) The right to indemnification and the payment of expenses incurred in defending a proceeding in advance of its final disposition conferred in this Article VIII shall not be exclusive of any other right which any person may have or hereafter acquire under any statute, provision of this amended and restated Certificate, by-law, agreement, vote of stockholders or disinterested directors or otherwise.

(e) The Corporation may maintain insurance, at its expense, to protect itself and any director, officer, employee or agent of the Corporation or another corporation, partnership, joint venture, trust or other enterprise against any such expense, liability or loss, whether or not the Corporation would have the power to indemnify such person against such expense, liability or loss under the DGCL.