CONSULTING AGREEMENT

Exhibit 10.2

CONSULTING AGREEMENT

This consulting agreement (the “Agreement”) is made as of June 7, 2012, by and between Horizon Lines, Inc. (hereinafter, the “Company”) and Stephen H. Fraser (hereinafter, the “Consultant”).

Whereas, Consultant has heretofore been employed as interim President and Chief Executive Officer of the Company and, as such, has become familiar with the Company, including its operations and facilities, its employees, its consultants and others with whom the Company has contractual relationships (together, the “Company Business”); and

Whereas, because of the knowledge and familiarity of Consultant with the Company Business, the Company wishes to retain Consultant on the terms and conditions contained in this Agreement to provide those consulting services provided for herein, and Consultant wishes to be so retained and to provide those services.

Now, therefore, for and in consideration of the premises, the mutual covenants and the payments to be made hereunder, and other good and valuable consideration, the receipt and sufficiency of which is hereby acknowledged, the Company and the Consultant each agrees as follows:

1. Term. The term of this agreement shall begin on June 12, 2012 (the “Effective Date”), shall run for one (1) year, and shall end on that date which is the first (1st) annual anniversary date of the Effective Date, unless terminated sooner by agreement of the parties or due to a default by a party as provided below. This Agreement may be extended by written agreement of the parties for such terms and with such modifications as the parties may agree.

2. Consulting Services. Consultant shall perform during the term hereof such consulting and/or advisory services for the Company as may reasonably be requested by the Company from time to time with respect to the management, technology, relationships and operation of the Company and its business.

Consultant will perform his obligations under this Agreement in such a manner as to attempt to enhance and improve the business of the Company and to foster the Company’s relationship with the past, existing and prospective customers, suppliers, contractors, consultants and/or vendors of the Company and its business. Consultant will provide advice to the employees of the Company with respect to its business and will share with the Company his knowledge regarding its business and operations.

The amount of time to be devoted by Consultant to providing consulting services hereunder, the specific time when such will be provided, and the method of how such will be provided shall be determined in the reasonable discretion of Consultant after consultation with the Company and as necessary to reasonably accomplish Consultant’s obligations hereunder; provided, however, that (A) such services shall be provided at such times as are reasonably acceptable to both Consultant and the Company and (B) Consultant shall be responsible for receiving instructions as to his services from any person reasonably authorized by the Board of Directors of the

Company to direct the services of Consultant, and (provided that such instructions are consistent with this Agreement) Consultant shall comply with such instructions.

3. Consideration. The Company shall pay to Consultant a retainer of $25,000 (the “Retainer”) within ten (10) days following the Effective Date, which the Consultant shall not be required to refund to the Company. The Consultant shall be paid for his services hereunder at a rate of $525 per hour, which fee shall be credited against the Retainer. Within ten (10) days following the end of each calendar month in which the Consultant performs services, the Consultant shall provide the Company with an accounting of all services performed and the hours worked by the Consultant in performing such services during such month. Until the fees credited to the Retainer equal $25,000, the Consultant shall not be paid any additional fee for the services that the Consultant performs hereunder. After the total fees credited to the retainer equal $25,000, the Company shall pay the Consultant any fees in excess of those previously credited to the Retainer (the “Excess Fees”). The Company shall pay the Excess Fees (if any) to the Consultant as soon as practicable following the Company’s receipt of the Consultant’s monthly accounting of services, but in no event later than 60 days following the end of each calendar month in which the Consultant performs services.

4. Expenses. The Company shall promptly reimburse the Consultant for all appropriately documented, reasonable business expenses incurred by the Consultant in the performance of services under this Agreement.

5. Default. A party shall be in default under this Agreement if that party fails to perform hereunder and fails to cure such failure to perform within ten (10) days of his/its receipt of written notice of such failure from the other party hereto. Should Consultant default under this Agreement, the Company may terminate this Agreement, in which case neither party shall have any obligations under items 2 or 3 of this Agreement with respect to time periods following termination, except that the Company shall remain obligated to pay amounts to Consultant due with respect to time periods ending at or before termination.

6. Independent Contractor Status. In performing Consultant’s obligations hereunder, Consultant is operating as an independent contractor and shall not, for any purpose, be deemed an employee or agent of the Company or be eligible to receive or qualify for any benefits offered by the Company to its employees. Consultant shall not be entitled to receive any benefits or payments not set forth in this agreement, and the parties hereto do not intend that any agency or partnership relationship be created between them by this Agreement. The Company shall not withhold any federal or state taxes or other applicable withholdings from amounts paid hereunder to Consultant, shall not issue to Consultant a form W-2 for payments made hereunder, and shall issue to Consultant the appropriate form 1099 for payments made hereunder.

7. Confidentiality and Restrictive Covenants.

A. Confidential Information. Consultant acknowledges that he has and will have access to confidential information (including, but not limited to, current and prospective confidential know-how, specialized training, customer lists, marketing plans, business plans, financial and pricing information, and information regarding acquisitions, mergers and/or joint ventures)

2

concerning the business, customers, clients, contacts, prospects, and assets of the Company and the Related Entities (as defined below) that is unique, valuable and not generally known outside the Company and/or the Related Entities, and which was obtained from the Company and/or the Related Entities or which was learned as a result of the performance of services by Consultant on behalf of the Company and/or the Related Entities (“Confidential Information”). “Confidential Information” does not include information that is in the public domain through no wrongful act on Consultant’s part. Consultant will not, at any time, directly or indirectly use, divulge, furnish or make accessible to any person any Confidential Information, but instead will keep all Confidential Information strictly and absolutely confidential; provided, however, that this provision shall not prevent Consultant from using his general business skill and knowledge in his future employment to the extent such skill and knowledge is not specifically related to the business of Company and its affiliates and is not used in Competition (as defined below), or otherwise prohibited under this section. Notwithstanding the foregoing, Consultant may disclose Confidential Information (i) that he is required by subpoena to disclose (provided that Consultant furnishes the Company with prompt written notice of receipt of such subpoena), or (ii) with the prior written consent of the Company. Consultant will deliver promptly to the Company, at the termination of his service relationship with the Company, or at any other time at the Company’s request, without retaining any copies (other than Consultant Records, as defined below), all documents and other materials in his possession relating, directly or indirectly, to any Confidential Information (subject to the last sentence in Section 7.E. below). For purposes of this Agreement, “Consultant Records” shall mean any written or electronic records of Consultant’s business and personal contacts.

B. Non-Competition. While Consultant is performing services for the Company, and for a period of six (6) months following the date of termination of his service relationship with the Company for any reason Consultant shall be prohibited from engaging in Competition with the Company, and its subsidiaries and affiliates (collectively, the “Related Entities”). The term “Competition” for purposes of this Agreement shall mean directly or indirectly, engaging in, holding any equity interest in, or managing or operating any person, firm, corporation, partnership or business (whether as director, officer, employee, agent, representative, partner, security holder, consultant or otherwise) that engages in a Jones Act business that competes with any business of the Company and the Related Entities anywhere in the world; with the exception of ownership of up to 1% of any class of securities of any publicly traded company. The Company and the Consultant may otherwise agree to modify or alter terms of this non-competition restriction, subject to the requirements of Section 11 of this Agreement.

C. Non-Solicitation of Employees. While Consultant is performing services for the Company, and for a period of six (6) months following the date of termination of his service relationship with the Company for any reason (the “Restricted Period”), Consultant shall not, without the prior written consent of the Company, directly or indirectly, hire or recruit or solicit the employment or services of (whether as an employee, officer, director, agent, consultant or independent contractor), any employee, officer, director, full-time consultant or independent contractor of the Company or the Related Entities (except in the course of his duties under this Agreement). Notwithstanding the foregoing, the Company agrees that it shall not be deemed a violation of this Section 7.C. for Consultant to respond to a request for a reference regarding any current or former employee of the Company or any of the Related Entities from such current or

3

former employee or from a third party, and providing a reference setting forth Consultant’s personal views about such current or former employee in connection with such request.

D. Non-Solicitation of Business Partners. During the Restricted Period, Consultant shall not, without the prior written consent of the Company, directly or indirectly, solicit or encourage, or attempt to solicit or encourage, any customers, suppliers, licensees, agents, consultants or independent contractors or other business partners or business affiliates of the Company or the Related Entities (collectively, “Business Partners”), to cease doing business with or modify their business relationship with the Company or the Related Entities, or in any way interfere with the relationship between any such Business Partner and the Company or the Related Entities (regardless of who initiates the contact).

E. Return of Company Property/Passwords. Consultant hereby expressly covenants and agrees that following termination of Consultant’s service relationship with the Company for any reason or at any time upon the Company’s request, Consultant will promptly return to the Company all property of the Company in his possession or control (whether maintained at his office, home or elsewhere), including, without limitation, all Company passwords, credit cards, keys, beepers, laptop computers, cell phones and all copies of all management studies, business or strategic plans, budgets, notebooks and other printed, typed or written materials, documents, diaries, calendars and data of or relating to the Company or its personnel or affairs, in whatever media maintained; provided, however, that Consultant shall be permitted to retain Consultant Records.

F. Remedies for Breach. Consultant acknowledges and agrees that a breach of this section would immediately and irreparably harm the Company and the Related Entities and that a remedy at law would be inadequate to compensate the Company and the Related Entities for their losses by reason of such breach and therefore that the Company and/or the Related Entities shall, in addition to any other rights and remedies available under this Agreement, at law or otherwise, be entitled to seek an injunction to be issued by any court of competent jurisdiction enjoining and restraining Consultant from committing any violation of this section, and Consultant hereby consents to the issuance of such injunction.

8. Severability/Construction. Whenever possible, each provision of this Agreement, or subpart thereof, shall be interpreted so as to be valid and effective under applicable law, but if any provision, or subpart thereof, of this Agreement shall be prohibited or invalid under applicable law, that provision, or subpart thereof, shall be ineffective only to the extent of the prohibition or invalidity, without invalidating the remainder of that provision or the remaining provisions of this Agreement. This Agreement is the product of joint drafting and shall not be interpreted against any party as the drafter of this Agreement. This Agreement shall be construed in accordance with and governed by the laws of the State of North Carolina, without reference to the conflicts or choice of law principles thereof. Any legal action or proceeding with respect to this Agreement may be brought in any federal or state court having Charlotte, North Carolina, as or within its jurisdiction or district. By execution of this Agreement, Consultant hereby submits to the jurisdiction and venue of said courts, hereby expressly waiving any defense of personal jurisdiction or improper venue. Nothing herein shall affect the right of any party to serve process in any manner permitted or required by law. The section headings or captions appearing in this

4

Agreement are for convenience only, are not part of this Agreement and are not to be considered in interpreting this Agreement.

9. Notices. All notices and other communications required or permitted hereunder shall be in writing and shall be deemed given when (A) delivered personally or by overnight courier to the following address of the other parties hereto (or such other address for such parties as shall be specified by notice given pursuant to this Section 9) or (B) sent by facsimile to the following facsimile number of the other parties hereto (or such other facsimile number for such parties as shall be specified by notice given pursuant to this Section 9), with the confirmatory copy delivered by overnight courier to the address of such parties pursuant to this Section 9.

If to the Company, to:

Horizon Lines, Inc.

4064 Colony Road, Suite 200

Charlotte, North Carolina 28211

Facsimile: (704)  ###-###-####

Attention: Board of Directors, Chairman

With a copy to:

Horizon Lines, Inc.

4064 Colony Road, Suite 200

Charlotte, North Carolina 28211

Facsimile: (704)  ###-###-####

Attention: General Counsel

If to Consultant:

Last address in the records of the Company

10. Binding Effect/Assignment/Waivers. This Agreement shall inure to the benefit of and be binding upon the heirs, estates, legal and personal representatives, successors and permitted assigns of the respective parties hereto. Consultant may not assign or delegate his rights, duties or obligations hereunder. Upon prior written notice to Consultant, the Company may assign or delegate its rights, duties or obligations hereunder in connection with any merger, sale or similar transaction. No waiver or release of any obligation or right of any party hereto shall be valid or enforceable unless made in writing and duly executed by all parties hereto. The terms of this Agreement shall survive the termination of this Agreement.

11. Entire Agreement/Modification. This Agreement, along with all items incorporated herein, constitutes the entire and complete agreement between the parties hereto and supersedes any prior oral or written agreement between the parties with respect to the obligations and covenants contemplated hereunder. It is expressly agreed that there are no verbal understandings or agreements which in any way change the terms, covenants, and conditions herein set forth, and

5

that no modification of this Agreement and no waiver of any of its terms and conditions shall be effective unless made in writing and duly executed by all parties hereto.

12. Counterparts. This Agreement may be executed in any number of identical counterparts, and each counterpart hereof shall be deemed to be an original instrument, but all counterparts hereof taken together shall constitute but a single instrument. This Agreement may be executed and delivered by facsimile transmission, and a facsimile copy of an executed counterpart shall be deemed and considered for all purposes as an original executed counterpart, in which case the parties then shall immediately circulate original documents for execution by all parties.

In witness whereof, the undersigned each have caused this Agreement to be executed under seal individually or by their duly authorized officers as of the date first set forth above.

6