RETIREMENT AGREEMENT

Exhibit 10.1

RETIREMENT AGREEMENT

     Horizon Lines, Inc. (the “Company”) and John W. Handy (“Executive”) enter into this Retirement Agreement (this “Agreement”) on the 21st day of January, 2009 (the “Agreement Date”).

W I T N E S S E T H:

     WHEREAS, Executive is employed by the Company as an Executive Vice President;

     WHEREAS, Executive has expressed a desire to retire early from his employment with the Company due to personal matters; and

     WHEREAS, the Company and Executive have agreed that as of January 31, 2009 (the “Retirement Date”) Executive shall retire and resign as Executive Vice President of the Company and from all other positions with the Company and its affiliates.

     NOW, THEREFORE, in consideration of the covenants and mutual promises contained in this Agreement, the parties agree as follows:

     1. Retirement Date. Effective on the Retirement Date, Executive’s service as an officer, employee, director or otherwise to the Company and all of its subsidiaries and affiliates shall terminate.

     2. Retirement Benefits. In consideration for Executive’s retirement and subject to Executive’s execution and non-revocation of this Agreement, the Company shall pay to Executive the following retirement benefits:

     (a) Retirement Payment. The Company will pay to Executive $388,881 in a single lump sum cash payment on the later of (i) the first business day following the Retirement Date, or (ii) the first business day following the end of the seven (7) day revocation period described in Section 6(b).

     (b) Treatment of Stock Options. Effective on the Retirement Date, the stock options awarded to Executive on April 7, 2006, March 26, 2007 and April 24, 2008 under the Horizon Lines, Inc. Amended and Restated Equity Incentive Plan (the “Plan”) shall become fully vested and immediately exercisable and such stock options shall remain exercisable until the respective expiration dates specified in the award agreements for such stock options. The award agreements for such stock options are hereby amended by the Stock Option Award Amendment attached to this Agreement as Exhibit A.

     (c) Treatment of Restricted Stock. Effective on the Retirement Date, the 70,000 restricted shares awarded to Executive under the Plan on February 2, 2006 (the “Restricted Stock”) shall be fully vested and nonforfeitable. The award agreement for the Restricted Stock is hereby amended by the Restricted Stock Award Amendment attached to this Agreement as Exhibit B. Effective on the Retirement Date, Executive shall forfeit

all outstanding and unvested shares of restricted stock (other than the Restricted Stock Award) that have been awarded to him under the Plan.

     The Company and Executive acknowledge and agree that Executive had no legally binding right to the benefits described in this Section 2 prior to the Agreement Date and such benefits are not intended to act as a substitute for, or replacement of, amounts earned by Executive under a “nonqualified deferred compensation plan” (as that term is defined in Section 409A of the Internal Revenue Code of 1986, as amended and applicable regulations thereunder).

     3. Other Compensation or Benefits. Executive acknowledges and agrees that, except as specifically set forth in this Agreement, following the Retirement Date, he is not and will not be due any compensation as an employee, including, but not limited to, compensation for unpaid salary (except for amounts unpaid and owing for Executive’s employment with the Company and its affiliates prior to the Retirement Date), unpaid bonus, severance and accrued or unused vacation time or vacation pay from the Company or any of its affiliates, and he will not be eligible to participate, except as a retired employee, in any of the compensation or benefit plans of the Company or any of its affiliates. Executive will be entitled to receive benefits, that are vested and accrued prior to the Retirement Date or which become vested or accrued under the provisions of this Agreement or pursuant to the employee benefit plans of the Company, and will be entitled to elect COBRA continuation coverage under the Company’s health and dental insurance plans. The Company shall promptly reimburse Executive for business expenses incurred in the ordinary course of Executive’s employment before the Retirement Date, in accordance with the Company’s expense reimbursement policies.

     4. Covenants

     (a) Noncompetition. For the period beginning on the Retirement Date and ending on January 31, 2010 (the “Restricted Period”), the Executive will not become a director, officer, employee or consultant for any business which is in competition with any line of business of the Company and its subsidiaries and affiliates (the “Company Group”) and which does business in the geographic footprint of the Company Group. Executive expressly acknowledges the reasonableness of such restrictions. Further, during the Restricted Period, Executive will not acquire an equity or equity-like interest in such an organization for Executive’s own account, except that Executive may acquire equity interests of not more than 5% of any such organization from time to time as an investment. Upon Executive’s request to the Company’s Chief Executive Officer, the Company will provide an advance opinion as to whether a proposed activity would violate the provisions of this Section 4(a).

     (b) Nonsolicitation. During the Restricted Period, Executive 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, agent, consultant or independent contractor of the Company Group. During the Restricted Period, Executive shall not, without prior written consent of the Company, directly or indirectly, solicit, attempt to do business with, do business with any business partners of, business affiliates of the Company Group, or encourage (regardless of who initiates the contact) any

customers of the Company Group to use the services of any competitor of the Company Group.

     (c) Confidentiality. Executive shall hold in fiduciary capacity for the benefit of the Company all secret, non-public or confidential information, knowledge or data relating to the Company Group and its related businesses, which shall have been obtained by Executive during Executive’s employment by the Company or any member of the Company Group. After the Retirement Date, Executive shall not, without the prior written consent of the Company or as may otherwise be required by law or legal process (including in connection with any arbitration or legal proceeding with regard to the enforcement of this Agreement), communicate or divulge any such information, knowledge or data to anyone other than the Company and those designated by it.

     (d) Return of Property. Executive will promptly after the Retirement Date return to the Company all reports, files, memoranda, records, computer equipment and software, credit cards, cardkey passes, door and file keys, computer access codes or disks and instructional manuals, and other physical or personal property which he received or prepared or helped prepare in connection with his employment with the Company, its subsidiaries and affiliates, and Executive will not retain any copies, duplicates, reproductions or excerpts thereof (other than material that is reasonably necessary to enable Executive to perform consulting services under a separate agreement with the Company).

     (e) Cooperation. If requested by the Company, Executive shall promptly, truthfully, and fully respond to all inquiries from the Company and its representatives (including its auditors, and/or attorneys), without requiring service of a subpoena, relating to any litigation or any inquiry by government agencies regarding Executive’s employment or events occurring during Executive’s employment. Executive shall cooperate in good faith with the Company in connection with any such legal and investigatory matters, including, without limitation, attending conferences and meetings as requested by the Company, and submitting to such interviews, depositions, or court testimony that may be requested by the Company or by a government agency. The Company agrees that it will reimburse Executive for any reasonable expenses, upon presentation of reasonably detailed receipts, incurred by Executive in connection with any such matters. The obligations set forth in this Section 4(e) apply during the period commencing on the Retirement Date and shall continue in full force and effect thereafter.

     (f) Non-Disparagement. Executive will refrain from taking any action or making any statements, written or oral, which are intended to or which disparage the business, goodwill or reputation of the Company or any member of the Company Group, or their respective directors, officers, executives or other employees, or which could adversely affect the morale of employees of the Company or any member of the Company Group (except to the extent required by applicable law, including under applicable securities laws).

     (g) Exit Checklist / Associate Questionnaire & Certification. Executive shall complete and return on or before the Retirement Date the Company’s Associate

Questionnaire & Certification, which is part of the Company’s Separating Associate Checklist.

     (h) Breach of Covenants. In the event of a breach or threatened breach of this Section 4, Executive agrees that the Company shall be entitled to seek injunctive relief in a court of appropriate jurisdiction to remedy any such breach or threatened breach and the Company may, in its sole discretion, terminate the exercise period of any unexercised stock options granted under the Company’s equity plans to Executive. Executive acknowledges that monetary damages would be an inadequate and insufficient remedy for a breach or threatened breach of this Section 4.

     (i) Subsequent Employment. Executive hereby agrees that prior to accepting employment with any other person or entity during the Restricted Period, the Executive will provide such prospective employer with written notice of the existence of this Agreement and the provisions of this Section 4, with a copy of such notice delivered simultaneously to the Company in accordance with the notice procedures of Section 10.

     5. General Release of Claims and Promise Not to Sue. To the maximum extent permitted by law and in consideration for the Company’s promises and obligations in this Agreement, Executive agrees for Executive and Executive’s heirs, successors, and assigns, hereby forever to release, discharge, and promise not to sue the Company, its parent, subsidiary, other affiliated entities, and all of its owners, shareholders, directors, officers, employees, agents, and employee benefit plans of such entities from or for any and all claims, debts, and causes of action of every kind and character whatever (including attorneys’ fees and costs) known or unknown which Executive has against such entities as of the execution of this Agreement, including without limitation any and all claims arising out of Executive’s employment with the Company or the ending of that employment, and any and all claims arising under federal, state, or local laws relating to employment, including without limitation claims of wrongful discharge, retaliation, breach of express or implied contract, fraud, misrepresentation, defamation, or liability in tort, claims of any kind that may be brought in any court or administrative agency, including without limitation claims under Title VII of the Civil Rights Act of 1964, the Americans with Disabilities Act, the Age Discrimination in Employment Act, the Employee Retirement Income Security Act, the Family and Medical Leave Act, and similar state or local statutes, ordinances, and regulations, provided, however, that this general release shall not extend to (i) claims for pension, retirement, or savings benefits which are or are required to be inalienable under the terms of any Company employee benefit plan and (ii) clams with respect to the enforcement of this Agreement, including rights to receive the indemnifications specified in Section 16 .

     6. Release of Age Discrimination Claims; Periods for Review and Reconsideration.

     (a) Executive understands and agrees that this Agreement includes a release of claims arising under the Age Discrimination in Employment Act (“ADEA”), and that this Agreement does not waive rights or claims that may arise after the date the waiver is executed. Executive understands that he has been given a period of twenty-one (21) days to review and consider this Agreement. Executive is hereby advised to consult with an attorney prior to executing the Agreement. By Executive’s signature below, Executive

represents that he has had the opportunity to be fully and fairly advised by that legal counsel as to the terms of the Agreement. Executive further understands that he may use as much or all of this 21-day period as he wishes before signing, and represents that he has done so.

     (b) Executive further understands that he has seven (7) days after signing this Agreement to revoke the Agreement by notice in writing to Mark Blankenship, Vice President — Human Resources (the “Company Contact”) in accordance with the notice procedures of Section 10. This Agreement shall be binding, effective, and enforceable upon Executive upon the expiration of this seven-day revocation period without the Company Contact having received such revocation, but not before such time. Executive understands and agrees that any payments hereunder shall not be made prior to the expiration of this seven-day revocation period.

     (c) Notwithstanding the provisions of Section 5, the promise not to sue contained therein shall not apply to claims arising under ADEA. However, the release contained therein shall apply in full to such claims.

     7. Executive’s Understanding. Executive acknowledges by signing this Agreement that Executive has read and understands this document, that Executive has conferred with or had opportunity to confer with Executive’s attorney regarding the terms and meaning of this Agreement, that Executive has had sufficient time to consider the terms provided for in this Agreement, that no representatives or inducements have been made to Executive except as set forth in this Agreement, and that Executive has signed the same knowingly and voluntarily.

     8. Non-Reliance. Executive represents to the Company and the Company represents to Executive that in executing this Agreement they do not rely and have not relied upon any representation or statement not set forth herein made by the other or by any of the other’s agents, representatives or attorneys with regard to the subject matter, basis or effect of this Agreement or otherwise.

     9. Severability of Provisions. In the event that any one or more of the provisions of this Agreement is held to be invalid, illegal or unenforceable, the validity, legality and enforceability of the remaining provisions will not in any way be affected or impaired thereby. Moreover, if any one or more of the provisions contained in this Agreement are held to be excessively broad as to duration, scope, activity or subject, such provisions will be construed by limiting and reducing them so as to be enforceable to the maximum extent compatible with applicable law.

     10. Notice. Any notice to be given hereunder shall be in writing and shall be deemed given when mailed by certified mail, return receipt requested, addressed as follows:

To Executive at:

To the Company at:

Horizon Lines, Inc.
4064 Colony Road, Suite 200
Charlotte, NC 28211
Attention: Mark Blankenship,
Vice President — Human Resources

With a copy to:

Horizon Lines, Inc.
4064 Colony Road, Suite 200
Charlotte, NC 28211
Attention: General Counsel

     11. Assignment. The Company may assign this Agreement to any other entity acquiring all or substantially all of the assets of the Company or to any other entity into which or with which the Company may be merged or consolidated. Upon such assignment, merger, or consolidation, the rights of the Company under this Agreement, as well as the obligations and liabilities of the Company hereunder, shall inure to the benefit of and be binding upon the assignee, successor-in-interest, or transferee of the Company. This Agreement is not assignable in any respect by Executive.

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

     13. Governing Law. This Agreement shall be governed by the statutes and common law of the State of North Carolina, without regard to its conflicts or choice of law principles. Except with respect to the Company’s right to injunctive relief for matters arising under Section 4 of this Agreement, Executive agrees that any dispute covered by the Company’s Dispute Resolution Program shall be brought pursuant to the terms of that program and that disputes between the parties not covered by the Dispute Resolution Program shall be brought exclusively in any of the State or Federal courts serving Mecklenburg County in the State of North Carolina.

     14. Withholding. All payments made under this Agreement shall be subject to the Company’s withholding of all required federal, state and local income and employment/payroll taxes (including FICA taxes), and all such payments shall be net of such tax withholding unless Executive makes other arrangements with the Company in advance for the payment of such tax withholding.

     15. Entire Agreement; Modification. This Agreement constitutes the entire agreement of the parties and supersedes all prior representations, proposals, discussions, and communications, whether oral or in writing. This Agreement may be modified only in writing and signed by both parties. This Agreement shall be enforceable in accordance with its terms when signed by the party sought to be bound.

     16. Indemnification/D&O Liability Insurance. Executive shall continue to be indemnified for acts and omissions occurring on or prior to the Retirement Date pursuant to the corporate governance documents of the Company and of any other member of the Company Group in accordance with their terms from time to time. Executive shall be covered under the Company’s directors’ and officers’ liability insurance policies in effect from time to time on the same basis that other former officers are covered.

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

EXHIBIT A

Stock Option Award Amendment

     WHEREAS, Horizon Lines, Inc., a Delaware corporation (the “Company”) has entered into Stock Option Award Agreements with John W. Handy (“Executive”), dated April 7, 2006, March 26, 2007 and April 24, 2008 (collectively, the “Option Agreements”);

     WHEREAS, Executive is employed by the Company as an Executive Vice President;

     WHEREAS, the Company and Executive have agreed that effective as of January 31, 2009 Executive shall retire and resign as Executive Vice President of the Company and from all other positions with the Company and its affiliates.

     WHEREAS, the Company and Executive have the authority to amend the Option Agreements pursuant to the terms and conditions of the Option Agreements; and

     WHEREAS, the Company and Executive have agreed to make certain modifications to the applicable vesting schedules and the exercise periods of the stock options granted to Executive pursuant to the Option Agreements.

     NOW THEREFORE, the Company and Executive agree to amend the Option Agreements in the following respects:

     1. The section entitled “Vesting Schedule” shall be amended in its entirety to read as follows:

“Vesting Schedule. The Option shall vest and become exercisable with respect to one hundred percent (100%) of the Shares covered by the Option on January 31, 2009.”

     2. The section entitled “Exercisability of Option” shall be amended by adding the following sentence to the end thereof:

“Notwithstanding anything in the Plan or this Stock Option Award Agreement to the contrary, the Option shall be exercisable until the last day of the Option Period.”

     3. In all other respects not amended, the Option Agreements are hereby ratified and confirmed.

EXHIBIT B

Restricted Stock Award Amendment

     WHEREAS, Horizon Lines, Inc., a Delaware corporation (the “Company”) has entered into a Restricted Stock Agreement with John W. Handy (“Executive”), dated February 1, 2006, (the “Agreement”);

     WHEREAS, Executive is employed by the Company as an Executive Vice President;

     WHEREAS, the Company and Executive have agreed that effective as of January 31, 2009 Executive shall retire and resign as Executive Vice President of the Company and from all other positions with the Company and its affiliates.

     WHEREAS, the Company and Executive have the authority to amend the Agreement; and

     WHEREAS, the Company and Executive have agreed to make certain modifications to the vesting schedule of the restricted stock granted to Executive pursuant to the Agreement.

     NOW THEREFORE, the Company and Executive agree to amend the Agreement in the following respects:

     1. Section 1(a) shall be amended by deleting it in its entirety and replacing it with the following:

“All 70,000 shares shall vest on January 31, 2009.

     2. Section 1(b) shall be amended by adding the following new sentence at the end thereof:

“Notwithstanding the foregoing, all dividends paid on or before January 31, 2009 pursuant to subsections (i) and (ii) above (and any earnings credited thereto) shall be paid to the Grantee in a single lump sum payment within seven business days following January 31, 2009.”

     3. In all other respects not amended, the Agreement is hereby ratified and confirmed.