Exhibit 23.1

CONSENT OF INDEPENDENT REGISTERED PUBLIC ACCOUNTING FIRM

We consent to the incorporation by reference in the following Registration Statements of Hawaiian Holdings, Inc. of our report dated February 18, 2010, with respect to the consolidated financial statements and schedule of Hawaiian Holdings, Inc., and the effectiveness of internal control over financial reporting of Hawaiian Holdings, Inc., included in this Annual Report (Form 10-K) for the year ended December 31, 2009:

(1)

Registration Statement (Form S-3 No. 333-133615)



(2)

Registration Statement (Form S-3 No. 333-162891),



(3)

Registration Statement (Form S-3 No. 333-163877),



(4)

Registration Statement (Form S-3 No. 333-129503),



(5)

Registration Statement (Form S-8 No. 333-127732),



(6)

Registration Statement (Form S-8 No. 333-127731),



(7)

Registration Statement (Form S-8 No. 333-09671),



(8)

Registration Statement (Form S-8 No. 333-09669),



(9)

Registration Statement (Form S-8 No. 333-61244), and



(10)

Registration Statement (Form S-8 No. 333-09667).

/s/ ERNST & YOUNG LLP

Honolulu, Hawaii
February 18, 2010

QuickLinks

Exhibit 23.1