Exhibit 23.1

Consent of Independent Registered Public Accounting Firm

     We consent to the incorporation by reference in the Registration Statement (Form S-8 No. 333-135552) pertaining to the Horizon Lines, Inc. Employee Stock Purchase Plan of our reports dated March 28, 2011, with respect to the consolidated financial statements and schedule of Horizon Lines, Inc., and the effectiveness of internal control over financial reporting of Horizon Lines, Inc., included in the Annual Report (Form 10-K) for the year ended December 26, 2010.

/s/ Ernst & Young LLP

Charlotte, North Carolina
March 28, 2011