Exhibit 23.1

Consent of Independent Registered Public Accounting Firm

We consent to the reference to our firm under the caption “Experts” in Amendment No. 1 to the Registration Statement (Form S-4 No. 333-176520) and related Prospectus of Horizon Lines, Inc. for the registration of $50,000,000 of common stock and $180,000,000 of 6.00% Series A convertible senior secured notes due 2017 and $100,000,000 of 6.00% Series B mandatorily convertible senior secured notes and to the use therein of our reports dated March 28, 2011, with respect to the consolidated financial statements and schedule of valuation and qualifying assets of Horizon Lines, Inc., and the effectiveness of internal control over financial reporting of Horizon Lines, Inc., included in its Annual Report (Form 10-K) for the year ended December 26, 2010 filed with the Securities and Exchange Commission.

/s/ Ernst & Young LLP

Charlotte, North Carolina

September 13, 2011