Exhibit 5.1

601 Lexington Avenue

New York, New York 10022

(212) 446-4800

www.kirkland.com

August 24, 2012

Horizon Lines, LLC

4064 Colony Road, Suite 200

Charlotte, North Carolina 28211

Re:    Registration Statement on Form S-4

Ladies and Gentlemen:

We are acting as special counsel to Horizon Lines, LLC, a Delaware limited liability company (the “Issuer”), Horizon Lines, Inc., a Delaware corporation (the “Company”), and each of the Company’s subsidiaries listed on Schedule A hereto (collectively, and together with the Company, the “Guarantors”), in connection with the preparation of the Registration Statement on Form S-4 (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 Issuer and the Guarantors. The Registration Statement relates to the proposed registration by the Issuer of (i) up to $223.9 million in aggregate principal amount of 11.00% First Lien Senior Secured Notes due 2016 of the Issuer (the “First Lien Exchange Notes”) to be guaranteed (the “First Lien Guarantees”) by the Guarantors and (ii) $147.9 million in aggregate principal amount of Second Lien Senior Secured Notes due 2016 (the “Second Lien Exchange Notes” and together with the First Lien Exchange Notes, the “Exchange Notes”) to be guaranteed (the “Second Lien Guarantee” and together with the First Lien Guarantees, the “Guarantees”) by the Guarantors. The First Lien Exchange Notes, the First Lien Guarantees, the Second Lien Exchange Notes and the Second Lien Guarantees are collectively referred to herein as the “Securities.”

The First Lien Exchange Notes and the Guarantees were issued pursuant to an indenture (the “First Lien Indenture”), dated as of October 5, 2011, by and between the Issuer, the guarantors thereto and U.S. National Bank Association, as trustee (the “Trustee”) and (ii) the Second Lien Exchange Notes and the Guarantees were issued pursuant to an indenture (the “Second Lien Indenture”), dated as of October 5, 2011, by and between the Issuer, the guarantors thereto and the Trustee. The Exchange Notes are to be issued in exchange for and in replacement of (i) the Issuer’s $223.9 million aggregate principal amount of 11.00% First Lien Senior Secured Notes due 2016 issued on October 5, 2012 (the “Old First Lien Notes”), and (ii) the Issuer’s $147.9 million aggregate principal amount of Second Lien Senior Secured Notes due 2016 issued on October 5, 2012 (the “Old Second Lien Notes” and, together with the First Lien Old Notes, the “Old Notes”). The First Lien Indenture and the Second Lien Indenture are referred to herein as the “Transaction Documents”.

Chicago Hong Kong London Los Angeles Munich Palo Alto San Francisco Shanghai Washington, D.C.

Horizon Lines, Inc.

August 24, 2012

Page 2

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 Issuer and the Guarantors, (ii) minutes and records of the corporate proceedings of the Issuer 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 Issuer and the Guarantors and the due authorization, execution and delivery of all documents by the parties thereto other than the Issuer 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 Issuer 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.

August 24, 2012

Page 3

(v) the Issuer 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 Exchange Notes constitute valid and binding obligations of the Issuer and are enforceable against the Issuer 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.

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 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

Horizon Lines, Inc.

August 24, 2012

Page 4

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 Exchange 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 Issuer and the Guarantors under the applicable Transaction Document may be dependent upon such matters, we assume for purposes of this opinion that the Trustee is duly organized, validly existing and in good standing under the laws of its jurisdiction of organization; that the Trustee 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 Trustee and constitutes the legally valid and binding obligations of such Trustee, enforceable against such Trustee in accordance with its terms; that the Trustee is in compliance, generally and with respect to acting as Trustee under the applicable Transaction Document, with all applicable laws and regulations; and that the Trustee 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.

Horizon Lines, Inc.

August 24, 2012

Page 5

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

Horizon Lines, Inc.

August 17, 2012

Page 6

Schedule A

Subsidiary Guarantors

Exact Name of Subsidiary	State of Incorporation or Organization
Horizon Lines Holding Corp.	Delaware
Hawaii Stevedores, Inc.	Hawaii
Horizon Lines of Puerto Rico, Inc.	Delaware
Horizon Lines of Alaska, LLC	Delaware
Horizon Lines of Guam, LLC	Delaware
Horizon Lines Vessels, LLC	Delaware
H-L Distribution Services, LLC	Delaware
Horizon Logistics, LLC	Delaware
Aero Logistics, LLC	Delaware
Sea-Logix, LLC	Delaware
Horizon Services Group, LLC	Delaware