Exhibit 5.1

Horizon Lines, Inc.

4064 Colony Road, Suite 200

Charlotte, North Carolina 28211

Re:    Registration Statement on Form S-1

Ladies and Gentlemen:

We are acting as special counsel to Horizon Lines, Inc., a Delaware corporation (the “Company”), and each of the Company’s subsidiaries listed on Schedule A hereto (collectively, the “Guarantors”), in connection with the preparation of the Registration Statement on Form S-1 (such Registration Statement, as amended or supplemented, is hereinafter referred to as the “Registration Statement”) filed with the Securities and Exchange Commission (the “Commission”) under the Securities Act of 1933, as amended (the “Securities Act”), by the Company and the Guarantors. The Registration Statement relates to the proposed registration by the Company of (i) $178,781,456 in aggregate principal amount of 6.00% Series A Convertible Senior Secured Notes due 2017 of the Company (the “Series A Notes”) to be guaranteed (the “Series A Guarantees”) by the Guarantors, (ii) $99,323,032 in aggregate principal amount of 6.00% Series B Mandatorily Convertible Senior Secured Notes (the “Series B Notes” and together with the Series A Notes, the “Notes”) to be guaranteed (the “Series B Guarantee” and together with the Series A Guarantees, the “Guarantees”) by the Guarantors, (iii) 2,420,231 shares of common stock, par value $0.01 per share, of the Company (the “Issued Common Stock”), (iv) 23,848,740 warrants to purchase shares of Common Stock upon exercise (the “Warrants”) and (v) 20,371,603 shares of the common stock of the Company issuable in respect of the Notes and the Warrants (the “Issuable Common Stock”), as each described in the Registration Statement. The Series A Notes, the Series A Guarantees, the Series B Notes, the Series B Guarantees, Issued Common Stock, Warrants and Issuable Common Stock are collectively referred to herein as the “Securities”.

The Notes and the Guarantees were issued pursuant to an indenture (the “Notes Indenture”), dated as of October 5, 2011, by and between the Company, the guarantors thereto and U.S. National Bank Association, as trustee (the “Trustee”) and (ii) the Warrants were issued pursuant to a warrant agreement, dated October 5, 2011, as amended on December 7, 2011, by and between the Company and The Bank of New York Trust Company, N.A., the warrant agent (the “Warrant Agreement”) and the Issued Common Stock were issued pursuant to a Registration Statement on Form S-4 filed by the Company and the Guarantors (File No. 33-176520 and File Nos. 333-176520-1 through 333-

Horizon Lines, Inc.

December 22, 2011

Page 2

176520-12) with the Commission and declared effective by the Commission as of October 3, 2011. The Notes Indenture and the Warrant Agreement are referred to herein as the “Transaction Documents”.

In connection with the registration of the Securities, we have examined originals, or copies certified or otherwise identified to our satisfaction, of such documents, corporate records and other instruments as we have deemed necessary for the purposes of this opinion, including (i) the organizational documents of the Company and the Guarantors, (ii) minutes and records of the corporate proceedings of the Company and the Guarantors, (iii) the Registration Statement and the exhibits thereto and (iv) the Transaction Documents.

For purposes of this opinion, we have assumed the authenticity of all documents submitted to us as originals, the conformity to the originals of all documents submitted to us as copies and the authenticity of the originals of all documents submitted to us as copies. We have also assumed the legal capacity of all natural persons, the genuineness of the signatures of persons signing all documents in connection with which this opinion is rendered, the authority of such persons signing on behalf of the parties thereto other than the Company and the Guarantors and the due authorization, execution and delivery of all documents by the parties thereto other than the Company and the Guarantors. We have not independently established or verified any facts relevant to the opinions expressed herein, but have relied upon statements and representations of the selling securityholders and officers and other representatives of the Company and the Guarantors.

We have also assumed that:

(i) the Registration Statement will be effective and will comply with all applicable laws at the time the Securities are offered or issued as contemplated by the Registration Statement;

(ii) any applicable prospectus supplement will have been prepared and filed with the Commission describing the Securities offered thereby to the extent necessary;

(iii) all Securities will be offered and sold in the manner stated in the Registration Statement or any applicable prospectus supplement;

(iv) the Securities were issued in accordance with, and in the form and containing the terms as set forth in, the Transaction Documents; and

Horizon Lines, Inc.

December 22, 2011

Page 3

(v) the Company will have obtained any legally required consents, approvals, authorizations and other orders of the Commission and any other federal regulatory agencies necessary for the Securities to be offered and sold in the manner stated in the Registration Statement or any applicable prospectus supplement.

Based upon and subject to the foregoing qualifications, assumptions and limitations and the further limitations set forth below, we are of the opinion that:

1. The Notes constitute valid and binding obligations of the Company and are enforceable against the Company in accordance with its terms.

2. The Guarantees constitute valid and binding obligations of the Guarantors and are enforceable against the respective Guarantor in accordance with their terms.

3. The Issued Common Stock have been validly issued, fully paid, and non-assessable.

4. The Warrants constitute valid and binding obligations of the Company and are enforceable against the Company in accordance with their terms.

5. The Issuable Common Stock issuable in respect of the Notes have been duly authorized and, when issued and delivered by the Company in accordance with the terms of the Notes and the Notes Indenture, will be validly issued, fully paid and non-assessable.

6. The Issuable Common Stock issuable in respect of the Warrants have been duly authorized and, when issued and delivered by the Company in accordance with the terms of the Warrants and the Warrant Agreement, will be validly issued, fully paid and non-assessable.

Our opinion expressed above is subject to the qualifications that we express no opinion as to the applicability of, compliance with, or effect of (i) any bankruptcy, insolvency, reorganization, fraudulent transfer, fraudulent conveyance, moratorium or other similar law affecting the enforcement of creditors’ rights generally (including, without limitation, Sections 547 and 548 of the United States Bankruptcy Code and Article 10 of the New York Debtor and Creditor Law), (ii) general principles of equity (regardless of whether enforcement is considered in a proceeding in equity or at law), (iii) public policy considerations which may limit the rights of parties to obtain certain remedies, and (iv) any laws except the laws of the State of New York and the Limited Liability Company Act of the State of Delaware and the Delaware General Corporation Law, including the applicable provisions of the Delaware constitution and reported judicial decisions interpreting these laws. For purposes of our opinion that the Guarantees will

Horizon Lines, Inc.

December 22, 2011

Page 4

be valid and binding obligations of the Guarantors, we have, without conducting any research or investigation with respect thereto, relied upon the opinion of Carlsmith Ball LLP with respect to Hawaii Stevedores, Inc. that such Guarantees have been duly authorized, executed and delivered, and do not conflict with, or require consents under, the corporate laws of Hawaii. We are not licensed to practice in Hawaii.

We express no opinion with respect to the enforceability of (i) consents to, or restrictions upon, judicial relief or jurisdiction or venue; (ii) waivers of rights or defenses with respect to stay, extension or usury laws; (iii) advance waivers of claims, defenses, rights granted by law, or notice, opportunity for hearing, evidentiary requirements, statutes of limitation, trial by jury or at law, or other procedural rights; (iv) waivers of broadly or vaguely stated rights; (v) provisions for exclusivity, election or cumulation of rights or remedies; (vi) provisions authorizing or validating conclusive or discretionary determinations; (vii) grants of setoff rights; (viii) provisions to the effect that a guarantor is liable as a primary obligor, and not as a surety; (ix) provisions for the payment of attorneys’ fees where such payment is contrary to law or public policy; (x) proxies, powers and trusts; (xi) restrictions upon non-written modifications and waivers; (xii) provisions prohibiting, restricting, or requiring consent to assignment or transfer of any right or property; (xiii) any provision to the extent it requires any party to indemnify any other person against loss in obtaining the currency due following a court judgment in another currency; and (xiv) provisions for liquidated damages, default interest, late charges, monetary penalties, make-whole premiums or other economic remedies to the extent such provisions are deemed to constitute a penalty. In addition, we express no opinion with respect to (i) whether acceleration of the Notes may affect the collectability of that portion of the stated principal amount thereof that might be determined to constitute unearned interest thereon, (ii) compliance with laws relating to permissible rates of interest or (iii) the creation, validity, perfection or priority of any security interest or lien.

To the extent that the obligations of the Company and the Guarantors under the applicable Transaction Document may be dependent upon such matters, we assume for purposes of this opinion that the respective Trustee or Warrant Agent is duly organized, validly existing and in good standing under the laws of its jurisdiction of organization; that the respective Trustee or Warrant Agent is duly qualified to engage in the activities contemplated by the applicable Transaction Document; that the applicable Transaction Document has been duly authorized, executed and delivered by the respective Trustee or Warrant Agent and constitutes the legally valid and binding obligations of such Trustee or Warrant Agent, enforceable against such Trustee or Warrant Agent in accordance with its terms; that the respective Trustee or Warrant Agent is in compliance, generally and with respect to acting as Trustee or Warrant Agent, as the case may be, under the applicable Transaction Document, with all applicable laws and regulations; and

Horizon Lines, Inc.

December 22, 2011

Page 5

that the respective Trustee or Warrant Agent has the requisite organizational and legal power and authority to perform its obligations under the applicable Transaction Document.

We hereby consent to the filing of this opinion with the Commission as Exhibit 5.1 to the Registration Statement. We also consent to the reference to our firm under the heading “Legal Matters” in the Registration Statement. In giving this consent, we do not thereby admit that we are in the category of persons whose consent is required under Section 7 of the Securities Act or the rules and regulations of the Commission. This opinion and consent may be incorporated by reference in a subsequent registration statement filed pursuant to Rule 462(b) of the rules promulgated under the Securities Act with respect to the registration of additional Securities for sale in any offering contemplated by the Registration Statement and shall cover such additional Securities.

We do not find it necessary for the purposes of this opinion, and accordingly we do not purport to cover herein, the application of the securities or “blue sky” laws of the various states to the sale of the Securities.

This opinion is limited to the specific issues addressed herein, and no opinion may be inferred or implied beyond that expressly stated herein. This opinion is limited to the laws, including the rules promulgated under the Securities Act, as in effect on the date on which the Registration Statement is declared effective by the Commission under the Securities Act, which laws are subject to change with possible retroactive effect. We assume no obligation to revise or supplement this opinion should the present federal securities laws, laws of the State of New York or the laws of the State of Delaware be changed by legislative action, judicial decision or otherwise.

This opinion is furnished to you in connection with the filing of the Registration Statement, and is not to be used, circulated, quoted or otherwise relied upon for any other purpose.

Sincerely,

/s/ Kirkland & Ellis LLP

Schedule A

Subsidiary Guarantors