EMPLOYMENT AGREEMENT

Exhibit 10.1

EMPLOYMENT AGREEMENT

This Employment Agreement (this “Agreement”) is entered into by and between Horizon Lines, Inc., a Delaware corporation (the “Company”), and Steven L. Rubin (“Executive”).

WHEREAS, prior to the Effective Date (as defined below), Executive has served as a non-employee member of the Company’s Board of Directors (the “Board”); and

WHEREAS, the Company has determined that it is in the best interests of the Company and its stockholders to enter into an employment agreement with Executive for Executive to serve as the Company’s Interim President and Chief Executive Officer and Executive is willing to serve as Interim President and Chief Executive Officer of the Company, subject to the terms and conditions of this Agreement.

NOW, THEREFORE, in consideration of the mutual covenants and agreements set forth below, it is hereby covenanted and agreed by Executive and the Company as follows:

1. Employment.

(a) Term. Effective June 27, 2014, Executive shall be appointed by the Board and thereafter be employed as Interim President and Chief Executive Officer of the Company. Such date will be the “Effective Date” of this Agreement. Executive’s employment under this Agreement shall commence as of the Effective Date and end when such employment is terminated by one of the parties in accordance with Section 5 below (the “Employment Term”).

(b) Duties. Executive shall report solely to the Board and shall perform his duties faithfully and efficiently and to the best of his abilities, subject to the directions of the Board. Executive shall devote substantially all of Executive’s business time and efforts to the performance of Executive’s assigned duties for the Company. Executive shall not accept any appointment as a director or engage in any significant business activities outside of the Company. The Company shall provide Executive with an office and administrative support at the Company’s headquarters commensurate with his position.

(c) Board Service. During the Employment Term, Executive shall continue to serve as a member of the Board; provided, however, that as of the Effective Date Executive shall and hereby does resign from his service as a member of the Audit Committee and Compensation Committee. Upon termination of the Employment Term, Executive shall resume service as a non-employee member of the Board.

2. Compensation.

(a) Base Salary. The Company shall pay Executive a base salary at the rate of $75,000 per month or such greater amount as the Board shall determine from time to time in its discretion (the “Salary”). Such Salary shall be payable in accordance with the Company’s standard payroll practices for senior executives.

(b) Board Compensation and Stock Ownership Requirements. During the Employment Term, (i) Executive shall continue to receive annual equity compensation awards equivalent to those granted to non-employee members of the Board, (ii) Executive shall continue to vest in his outstanding equity awards as if he remained a non-employee member of the Board during the Employment Term and (iii) the payment of the annual cash retainer to Executive for his Board service shall be prorated to reflect only Executive’s service as a non-employee member of the Board for the year for which such retainer is paid. During the Employment Term, Executive shall remain subject to such stock ownership requirements applicable to non-employee members of the Board, but not to the stock ownership requirements applicable to executives of the Company.

(c) Benefits. During the Employment Term, Executive shall be eligible to participate in the employee benefit plans generally available to senior executives of the Company, to the extent Executive meets the eligibility requirements of any such plans, and, in any event, subject to the terms of the applicable plans; provided, however, that (i) except as provided in this Agreement, Executive shall not be entitled to receive any severance benefits or participate in the Company’s equity compensation program generally available to senior executives of the Company and (ii) in lieu of Executive’s participation in the Company’s group medical plan during all or any portion of the Employment Term, Executive may elect that the Company reimburse Executive for the premiums paid by Executive for the medical coverage of Executive and his dependents under the plan or policy in effect for their benefit as of the Effective Date. Executive shall be entitled to take time off for vacation or illness in accordance with the Company’s policy for senior executives and to receive all other fringe benefits as are from time to time made generally available to senior executives of the Company. Nothing herein shall affect the Company’s right to alter, suspend, amend or discontinue any and all of its benefit plans, fringe benefits or policies, in whole or in part, at any time with or without notice in accordance with applicable law.

(d) Legal Fees. The Company shall reimburse Executive for legal fees and expenses incurred by Executive up to $10,000 in connection with the negotiation and review of this Agreement and any documents ancillary thereto.

(e) Expense Reimbursement. During the Employment Term, the Company shall reimburse Executive, in accordance with the Company’s policies and procedures, for all expenses incurred by Executive in the performance of Executive’s duties hereunder.

3. Federal and State Withholding. The Company shall deduct from the amounts payable to Executive pursuant to this Agreement the amount of all required federal, state and local withholding taxes in accordance with Executive’s Form W-4 on file with the Company, and all applicable federal employment taxes.

4. Indemnification. To the fullest extent permitted by the indemnification provisions of the laws of the state or jurisdiction of the Company’s incorporation in effect from time to time, and subject to the conditions thereof, the Company shall (i) indemnify Executive, as a director and officer of the Company or a trustee or fiduciary of an employee benefit plan of the Company against all liabilities and reasonable expenses that Executive may incur in any threatened, pending, or completed action, suit or proceeding, whether civil, criminal or administrative, or investigative and whether formal or informal, because Executive is or was a director or officer of the Company or a trustee or fiduciary of such employee benefit plan, and (ii) pay for or reimburse the reasonable expenses upon submission of appropriate documentation incurred by Executive in the defense of any proceeding to which Executive is a party because Executive is or was a director or officer of the Company or a trustee or fiduciary of such employee benefit plan, including an advancement of such expenses to the extent permitted by applicable law, subject to Executive’s execution of any legally required repayment undertaking. The preceding indemnification right shall be in addition to, and not in lieu of, any rights to indemnification to which Executive may be entitled under the certificate of incorporation and bylaws of the Company in effect from time to time. The indemnification rights of Executive in this Section 4 are referred to below as the “Indemnification Provisions.” The rights of Executive under the Indemnification Provisions shall survive the cessation of Executive’s employment with the Company. The Company shall maintain a directors’ and officers’ liability insurance policy, or an equivalent errors and omissions liability insurance policy, covering Executive with scope, exclusions, amounts and deductibles no less favorable to the insured than those applicable to the Company’s senior officers and directors on the Effective Date, or any more favorable as may be available to any other director or senior executive of the Company, while Executive is employed with the Company and thereafter until the sixth anniversary of Executive’s termination date.

5. Termination. Executive’s employment under this Agreement may be terminated by the Company or by Executive under the following circumstances:

(a) Death. Executive’s employment hereunder shall automatically terminate upon Executive’s death.

(b) Disability. If Executive becomes Disabled, the Company may terminate Executive’s employment. “Disabled” means Executive’s inability to perform the essential functions and duties of Executive’s position with the Company, with or without reasonable accommodation, as a result of any physical or mental impairment, as determined by the Board upon certification thereof by a qualified physician selected by the Board.

(c) Cause. The Company may terminate Executive’s employment hereunder for Cause. For purposes of this Agreement, “Cause” means (i) Executive’s willful and continued failure to attempt in good faith (other than as a result of incapacity due to mental or physical impairment) to substantially perform the duties of his position, and such failure is not remedied within thirty (30) days after receipt of written notice from the Board specifying such failure; (ii) Executive’s failure to attempt in good faith to carry out, or comply with, in any material respect any lawful and reasonable directive of the Board consistent with the duties of his position, which is not remedied within thirty (30) days after receipt of written notice from the Board specifying such failure; (iii) a material breach by Executive of the Company’s code of ethics, which is not remedied within thirty (30) days after receipt of written notice from the Board or the Chief Executive specifying such failure; (iv) Executive’s conviction, plea of no contest or plea of nolo contendere, or imposition of unadjudicated probation for any felony (other than a traffic violation or arising purely as a result of Executive’s position with the Company); (v) Executive’s knowing unlawful use (including being under the influence) or possession of illegal drugs; or (vi) Executive’s commission of an act of fraud, embezzlement, misappropriation, willful misconduct, gross negligence, or breach of fiduciary duty, in each case against the Company.

(d) Without Cause. The Company may terminate Executive’s employment under this Agreement without Cause upon ninety (90) days advance notice to Executive.

(e) Resignation. Executive may resign his employment upon ninety (90) day advance notice to the Company. Upon receiving such notice, the Company is entitled to make such resignation effective at any time on or prior to the resignation date proposed by Executive and such action shall not be deemed a termination without Cause.

6. Compensation Upon Termination. Subject to Section 2(b), upon the termination of Executive’s employment, Executive (or his estate, heirs or beneficiaries, as applicable) shall be entitled to (a) payment of any earned, but unpaid Salary, (b) payment of any accrued but unused vacation or paid time off, and (c) other employee benefits to which Executive is entitled upon termination of employment in accordance with the terms of the applicable plans and programs of the Company. In addition, if within one year of the Effective Date of this Agreement the Company provides executive with notice that it is terminating Executive’s employment without Cause, Executive continues to comply with this Agreement, Executive continues to work until the end of the notice period and Executive signs within forty-five (45) days of receipt from the Company and does not revoke a release of claims against the Company, and its affiliates, as well as its respective present and former officers, directors, managers, owners, employees, agents, benefit

plans, successors, predecessors and assigns, in form and substance satisfactory to the Company (the “Release”), then the Company will pay Executive a lump sum amount equal to six months of Executive’s Salary to Executive (the “Severance Payment”). If the conditions described above are satisfied, the Severance Payment will be paid to Executive on the sixtieth (60^th) day after the date on which his employment terminated. Executive shall not be entitled to any severance should the Company provide notice it intends to terminate Executive’s employment without Cause more than one year after the Effective Date of this Agreement.

7. 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) 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), with the confirmatory copy delivered by overnight courier to the address of such parties pursuant to this Section 7.

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 Executive, to:

Last address in records of Company

or to such other address as may have been furnished by a party hereto to the other party hereto, by like notice.

8. Severability. Whenever possible, each provision of this Agreement shall be interpreted in such manner as to be effective and valid under applicable law, but if any provision of this Agreement is held to be invalid, illegal or unenforceable in any respect under applicable law or rule in any jurisdiction, such invalidity, illegality or

unenforceability shall not affect the validity, legality or enforceability of any other provision of this Agreement or the validity, legality or enforceability of such provision in any other jurisdiction, but this Agreement shall be reformed, construed and enforced in such jurisdiction as if such invalid, illegal or unenforceable provision had never been contained herein.

9. Entire Agreement. This Agreement constitutes the entire agreement and understanding between the parties with respect to the subject matter hereof and supersedes and preempts any prior understandings, agreements or representations by or between the parties, written or oral, which may have related in any manner to the subject matter hereof.

10. Successors and Assigns. This Agreement shall be enforceable by Executive and Executive’s heirs, executors, administrators and legal representatives, and by the Company and its successors and assigns. The Company shall have the right to assign or transfer this Agreement to any affiliated entity or any successor, and Executive irrevocably consents to any such assignment or transfer. Executive may not assign this Agreement and any such assignment shall be null and void.

11. Governing Law. This Agreement shall be governed, construed, interpreted and enforced in accordance with the substantive laws of the State of Delaware, without reference to principles of conflicts or choice of law under which the law of any other jurisdiction would apply.

12. Disputes. Any dispute or controversy arising under, out of, in connection with or in relation to this Agreement shall, at the election and upon written demand of any party to this Agreement, be finally determined and settled by arbitration in Charlotte, North Carolina, or any other location mutually agreed upon by the parties, in accordance with the rules and procedures of the American Arbitration Association, and judgment upon the award may be entered in any court having jurisdiction thereof.

13. Section 409A of the Code. This Agreement is intended to comply with the requirements of Section 409A of the Internal Revenue Code of 1986, as amended (the “Code”), and shall be interpreted and construed consistently with such intent. The payments to Executive pursuant to this Agreement are also intended to be exempt from Section 409A of the Code to the maximum extent possible as short-term deferrals pursuant to Treasury regulation §1.409A-1(b)(4). In the event the terms of this Agreement would subject Executive to taxes or penalties under Section 409A of the Code (“409A Penalties”), the Company and Executive shall cooperate diligently to amend the terms of the Agreement to avoid such 409A Penalties, to the extent possible. Any reimbursement or advancement payable to Executive pursuant to this Agreement shall be conditioned on the submission by Executive of all expense reports reasonably required by the Company under any applicable expense reimbursement policy, and shall be paid to Executive within 30 days following receipt of such expense reports, but in no event later than the last day of the

calendar year following the calendar year in which Executive incurred the reimbursable expense. Any amount of expenses eligible for reimbursement, or in-kind benefit provided, during a calendar year shall not affect the amount of expenses eligible for reimbursement, or in-kind benefit to be provided, during any other calendar year. The right to any reimbursement or in-kind benefit pursuant to this Agreement shall not be subject to liquidation or exchange for any other benefit.

14. Amendment and Waiver. The provisions of this Agreement may be amended or waived only by the written agreement of the Company and Executive, and no course of conduct or failure or delay in enforcing the provisions of this Agreement shall affect the validity, binding effect or enforceability of this Agreement.

15. Counterparts. This Agreement may be executed in two or more counterparts, each of which shall be deemed to be an original and all of which together shall constitute one and the same instrument.

[SIGNATURE PAGE TO FOLLOW]

IN WITNESS WHEREOF, the parties hereto have executed this Agreement as of the date first written above.