QuickLinks -- Click here to rapidly navigate through this document

Exhibit 5.1

[Letterhead of Paul, Weiss, Rifkind, Wharton & Garrison]

        July 22, 2002

(212) 373-3000

(212) 757-3990

Hawaiian Holdings, Inc.
3375 Koapaka Street, Suite G-350
Honolulu, Hawaii 96810

        Hawaiian Holdings, Inc.
Registration Statement on Form S-4
File No. 333-87540

Ladies and Gentlemen:

        We have acted as special counsel to Hawaiian Holdings, Inc., a Delaware corporation (the "Company"), in connection with the transactions described in the above-captioned Registration Statement on Form S-4 (the "Registration Statement") filed by the Company with the Securities and Exchange Commission under the Securities Act of 1933, as amended (the "Act"), and the rules and regulations under the Act (the "Rules"). This opinion is being furnished at the request of the Company regarding the legality of up to 19,538,861 shares (the "Public Shares") of the Company's common stock, par value $0.01 per share (the "Common Stock"), registered for sale under the Registration Statement and up to 18,181,818 shares of Common Stock (the "AIP LLC Shares") issuable under the AIP Merger Agreement (as defined below).

        In connection with the furnishing of this opinion, we have examined originals, or copies certified or otherwise identified to our satisfaction, of the following documents:

1.

the Registration Statement;

2.

the Agreement and Plan of Merger, dated as of May 2, 2002, by and among the Company, Hawaiian Airlines, Inc. and HA Sub Inc.; and

3.

the Agreement and Plan of Merger, dated as of May 2, 2002, by and among the Company, Hawaiian Holdings, Inc., AIP General Partner, Inc. and AIP Merger Sub, Inc (the "AIP Merger Agreement").

        In addition, we have examined: (i) such corporate records of the Company as we have considered appropriate, including a copy of the certificate of incorporation, as amended, and by-laws of the Company as certified by the Company, copies of the form of the amended and restated certificate of incorporation and the form of the amended by-laws of the Company to be filed and become effective immediately prior to the effective time of the reorganization (as used in the Registration Statement) and copies of resolutions of the board of directors of the Company relating to the issuance of the Public Shares and the AIP LLC Shares; and (ii) such other certificates, agreements and documents as we deemed relevant and necessary as a basis for the opinions expressed below.

        In our examination of the documents referred to above, we have assumed, without independent investigation, the genuineness of all signatures, the legal capacity of all individuals who have executed any of the documents reviewed by us, the authenticity of all documents submitted to us as originals, the conformity to the original documents of all documents submitted to us as certified, photostatic, reproduced or conformed copies of valid existing agreements or other documents, the authenticity of the latter documents and that statements regarding matters of fact in the certificates, records, agreements, instruments, and documents that we have examined are accurate and complete.

        Based upon the foregoing, and subject to the assumptions, exceptions and qualifications set forth in this letter, we are of the opinion that, upon the filing and effectiveness of the Company's amended and restated certificate of incorporation, the Public Shares and the AIP LLC Shares have been duly authorized by all necessary corporate action on the part of the Company and, when issued and delivered and paid for in accordance with the documents referred to above, will be validly issued, fully paid and non-assessable.

        Our opinion expressed above is limited to the General Corporation Law of the State of Delaware. Our opinion is rendered only with respect to the laws, and the rules, regulations and orders under those laws. Please be advised that no member of this firm is admitted to practice in the State of Delaware. This letter is furnished by us for your benefit in connection with the transactions referred to in the Registration Statement and may not be circulated to any other person without our prior written consent.

        We consent to the filing of this letter as an exhibit to the Registration Statement and to the reference to our name under the caption "Legal Opinions" in the proxy statement/prospectus included in the Registration Statement. In giving this consent, we do not agree or admit that we come within the category of persons whose consent is required by the Act or the Rules.

Very truly yours,

        /s/ PAUL, WEISS, RIFKIND, WHARTON & GARRISON

        PAUL, WEISS, RIFKIND, WHARTON & GARRISON

2

QuickLinks

Exhibit 5.1