United Continental Holdings, Inc. (UAL): PAR Capital, Altimeter Capital Express Governance Concerns, Put Forth Minority Board Slate

UNITED STATES

SECURITIES AND EXCHANGE COMMISSION

Washington, D.C. 20549

SCHEDULE 13D

Under the Securities Exchange Act of 1934

(Amendment No. 2)*

United
Continental Holdings, Inc.

(Name of Issuer)

Common Stock, $0.01 par value

(Title of Class of Securities)

910047109

(CUSIP Number)

PAR Capital Management, Inc.

Attn: Steven M. Smith

One International Place, Suite 2401

Boston, MA 02110

(617)
526-8990

(Name, Address and Telephone Number of Person Authorized to Receive Notices and Communications)

March 8, 2016

(Date of
Event which Requires Filing of this Statement)

If the filing person has
previously filed a statement on Schedule 13G to report the acquisition that is the subject of this Schedule 13D, and is filing this schedule because of §§240.13d-1(e), 240.13d-1(f) or 240.13d-1(g), check the following
box:  ¨

Note: Schedules filed in paper format shall
include a signed original and five copies of the schedule, including all exhibits. See §240.13d-7 for other parties to whom copies are to be sent.

The information required on the remainder of this cover page shall not be
deemed to be filed for the purpose of Section 18 of the Securities Exchange Act of 1934 (Act) or otherwise subject to the liabilities of that section of the Act but shall be subject to all other provisions of the Act
(however, see the Notes).

This Amendment No.2 (this Amendment) to Schedule 13D (as amended to date, the
Schedule 13D) is being filed by PAR Investment Partners, L.P., a Delaware limited partnership (PAR Investment Partners), PAR Group, L.P., a Delaware limited partnership (PAR Group), and PAR
Capital Management, Inc., a Delaware corporation (PAR Capital Management). PAR Investment Partners, PAR Group and PAR Capital Management are sometimes individually referred to herein as a Reporting Person and
collectively as the Reporting Persons. Capitalized terms used but not otherwise defined in this Amendment shall have the meanings ascribed to them in the Schedule 13D. Except as otherwise specifically amended in this Amendment,
items in the Schedule 13D remain unchanged.

Item 3 of Schedule 13D is hereby amended and
restated as follows:

PAR Investment Partners used approximately $722,699,041 (including brokerage commissions) of the working capital of PAR Investment
Partners in the aggregate to purchase the shares of Common Stock reported in this Schedule 13D. Such shares of Common Stock are or may be held from time to time by PAR Investment Partners in margin accounts established with its brokers or banks and
a portion of the purchase price for the Common Stock may be obtained through margin borrowing. Securities positions which may be held in the margin accounts, including the Common Stock, may be pledged as collateral security for the repayment of
debit balances in the margin accounts.

Item 4 of Schedule 13D is hereby amended by adding the following paragraph
to the end thereof:

On March 8, 2016, Altimeter Capital Management, LP (Altimeter Capital Management) and PAR Capital Management
issued a joint press release (the Joint Press Release) disclosing their intention to encourage the Issuers stockholders to elect at the Issuers 2016 annual meeting of stockholders (the Annual
Meeting) a minority board slate nominated by Altimeter Capital Management and its affiliates (Altimeter). Altimeter has submitted to the Issuer a notice of its intention to nominate Brenda Yester Baty, Gordon Bethune,
Brad Gerstner, Barnaby Harford (Mr. Harford), Rodney ONeal and Tina Beth Sharkey for election to the Issuers board of directors at the Annual Meeting. Along with this formal minority-slate nomination notice, on
March 8, 2016 Altimeter Capital Management and PAR Capital Management also delivered a letter highlighting concerns about the Issuers board composition, the boards record, and the Issuers resulting long-term underperformance.

A copy of the Joint Press Release is attached as Exhibit 99.2 to this Schedule 13D and is incorporated by reference herein.

Item 5 of Schedule 13D is hereby amended and restated as
follows:

(a)-(b) As of March 8, 2016, PAR Investment Partners may be deemed to beneficially own 14,389,711shares of Common Stock, representing
approximately 4.0% (determined in accordance with Rule 13d-3 under the Act) of the outstanding Common Stock.

As of March 8, 2016, PAR Group, through
its control of PAR Investment Partners as general partner, may be deemed to beneficially own 14,389,711shares of Common Stock, representing approximately 4.0% (determined in accordance with Rule 13d-3 under the Act) of the outstanding Common Stock.

As of March 8, 2016, PAR Capital Management, through is control of PAR Group as general partner, may be
deemed to beneficially own 14,389,711shares of Common Stock, representing approximately 4.0% (determined in accordance with Rule 13d-3 under the Act) of the outstanding Common Stock.

The percentage of shares beneficially owned as set forth in row 13 is based on 359,484,808 shares of common stock of the Issuer outstanding as of
February 9, 2016, as disclosed in the Issuers Annual Report on Form 10-K, for the year ended December 31, 2015, filed on February 18, 2016.

Representatives of the Reporting Persons have engaged in discussions with Altimeter regarding strategies to enhance shareholder value of the Issuer. As a
result, and by reason of Altimeters intention to nominate Mr. Harford for election to the Issuers board of directors, the Reporting Persons may be deemed members of a group with Altimeter and Mr. Harford as defined
in Rule 13d-5 of the Securities Exchange Act of 1934, as amended (the Exchange Act). Pursuant to such definition, the Reporting Persons, Altimeter and Mr. Harford may be deemed to beneficially own the shares of Common Stock
beneficially owned by each other solely for such purposes. Altimeter and Mr. Harford have advised the Reporting Persons that they are the beneficial owner of 11,509,268 and 40,000 shares of Common Stock, or 3.2% and less than 0.1% of the
outstanding Common Stock, respectively. Based upon such advice, the Reporting Persons and Altimeter beneficially own a combined 25,938,979 shares of Common Stock, or 7.2% of the outstanding Common Stock. The Reporting Persons expressly disclaim
beneficial ownership of any shares of Common Stock held by Altimeter, Mr. Harford and/or their respective affiliates. Accordingly, Items 11 and 13 of the cover pages to this Schedule 13D set forth the aggregate number and percentage of
outstanding shares of Common Stock that are beneficially owned by the Reporting Persons.

The Reporting Persons (i) own (and will continue to own)
less than 5% of the total outstanding Common Stock for purposes of Treasury Regulation Section 1.382-2T(g), (ii) have the sole right to dividends and/or proceeds from the sale of the Common Stock reported in Item 11 of this Schedule
13D and have no dividend or voting rights in any other shares of Common Stock, and (iii) do not have any formal or informal understanding with Altimeter, Mr. Harford or any other stockholder of the Issuer to make any coordinated
acquisitions of, or investment decisions with respect to, the Common Stock.

(c) Information with respect to all transactions by the Reporting Persons
relating to the Common Stock that were effected during the past sixty days is set forth in Annex A hereto and is incorporated by reference herein.

(d) Not applicable.

(e) Not applicable.

Item 6. CONTRACTS, ARRANGEMENTS, UNDERSTANDINGS OR RELATIONSHIPS WITH RESPECT TO SECURITIES OF THE ISSUER

Item 6 of Schedule 13D is hereby amended and restated as follows:

PAR Investment Partners holds a portion of its assets, which may include the Issuers securities, in prime brokerage accounts at various institutions,
which accounts provide PAR Investment Partners with access to margin or other financing. The customer and related agreements governing such accounts generally provide the broker counterparty with security, collateral or similar rights of possession,
sale or offset with respect to such account assets in the event of a customer default. Such agreements generally also provide the counterparty with rights to lend assets held in such account, in some cases without advance or other notification to
the customer. To the extent the Issuers securities owned by PAR Investment Partners are held from time to time in such prime broker accounts, they may be subject to such counterparty rights.

The Reporting Persons and Altimeter have orally agreed to share equally the costs and expenses with respect to the matters disclosed in the Joint Press
Release. It is anticipated that such costs and expenses will include those related to the solicitation of proxies, including expected expenditures for attorneys, accountants, public relations and financial advisors, proxy solicitors, advertising,
printing, transportation, litigation and related expenses.

The Reporting Persons are parties to an agreement with respect to the joint filing of this Schedule 13D and any
amendments thereto. A copy of such agreement is attached as Exhibit 99.1 to the Schedule 13D and is incorporated by reference herein.

Except as set forth
herein, there are no contracts, arrangements, understandings or relationships among the Reporting Persons or between the Reporting Persons and any other person with respect to the Common Stock.

SIGNATURE

After reasonable inquiry and to the best of my knowledge and belief, I certify that the information set forth in this statement is true, complete and correct.

Date: March 8, 2016

Annex A

TRANSACTIONS IN COMMON STOCK BY THE REPORTING PERSONS

The following tables set forth all transactions relating to the Common Stock effected by the Reporting Persons in the past sixty days that have not been
previously reported on Schedule 13D. Unless otherwise noted, all such transactions were effected in the open market through a broker and all prices per share include commissions.

PAR Investment Partners, L.P.