EMPLOYMENT AGREEMENT

Exhibit 10.1

EMPLOYMENT AGREEMENT

This EMPLOYMENT AGREEMENT (the “Agreement”) is made as of June 7, 2012 (the “Agreement Date”), between HORIZON LINES, INC., a Delaware corporation (the “Company”), and Samuel A. Woodward (“Executive”).

The Company desires to retain Executive’s services as set forth in the Agreement and to provide the necessary consideration to assure such services. The Company and Executive therefore agree as follows:

1. Employment. The Company hereby employs Executive as its President and Chief Executive Officer, reporting directly to the Board of Directors of the Company (the “Board”) and having such powers and duties as may reasonably be assigned by the Board and consistent with the position of President and Chief Executive Officer. Executive hereby accepts the employment specified herein, agrees to perform, in good faith, the duties, consistent with his position, prescribed by the Board hereunder, abide by the terms and conditions described in this Agreement and to devote his full working time and best efforts to the Company. Exhibit A to this Agreement sets forth the corporate, civic or charitable boards Executive currently serves on, and after obtaining the prior approval of the Board, Executive may serve on additional corporate, civic or charitable boards not listed on Exhibit A, provided that, in the reasonable opinion of the Board, such additional board membership activities (taking into account all existing board memberships) do not individually or in the aggregate interfere with the performance of his duties and responsibilities under this Agreement or create real or apparent conflict of interests. The Company agrees to appoint Executive to the Board and to thereafter nominate Executive for election to the Board as a member of the management slate at each annual meeting of stockholders during Term at which Executive’s director class stands for election. Executive agrees to serve on the Board.

2. Term of Employment. The term of employment under this Agreement (the “Term”) shall commence on the Agreement Date and shall expire on June 30, 2015; provided that on April 1, 2015, and on each subsequent anniversary thereof, the Term shall be deemed to have been extended by the parties for an additional one-year period at the end of the then-current Term, unless either party gives written notice to the other party, prior to April 1, 2015, or an anniversary thereof, of its election not to extend the Term.

3. Location of Employment. Executive will be based and work primarily at the Company’s principal executive offices in Charlotte, North Carolina. During the period from the Agreement Date to the six month anniversary of the Agreement date, the Company will reimburse Executive for reasonable expenses related to travel between his current residence and Charlotte, North Carolina. The Company will provide Executive with relocation assistance in accordance with the Company’s Buyer Value Option Homeowner Relocation Policy.

4. Compensation. During the Term, the Executive shall be paid the compensation and be provided with the benefits described below:

(a) Annual Base Salary. The Company shall pay Executive a base salary at the rate of $600,000 per annum or such greater amount as the Board shall determine from time to time in its discretion (the “Base Salary”). Such Base Salary shall be payable in accordance with the Company’s standard payroll practices for senior executives, and may not be decreased without Executive’s prior written consent.

(b) Annual Bonus Opportunity. Executive shall have the opportunity to earn a cash bonus for each calendar year during the Term (the “Annual Bonus”), based on achievement of performance goals for the fiscal year of the Company ending within such calendar year (the “Performance Year”), if Executive remains in continuous employment to the last day of such calendar year (or, if earlier, to the date on which the Term expires). The performance goals for a Performance Year shall be established by the Board (or the Compensation Committee of the Board) in its discretion, after consultation with Executive and consideration of current business conditions. The Annual Bonus amount shall be up to 100% of Executive’s Base Salary for the calendar year if the target levels for performance goals for the Performance Year are achieved, and shall be 133% of Base Salary for the calendar year if the maximum levels for performance goals for the Performance Year are achieved. The Board (or the Compensation Committee of the Board) may provide for a range of Annual Bonus amounts of less than 100% of Base Salary for achievement of performance goals between threshold performance levels and target performance levels, and a range of Annual Bonus amounts greater than 100% but less than 133% of Base Salary for achievement of performance goals between target performance levels and maximum performance levels. The Annual Bonus shall be payable in a lump sum within thirty (30) days following the final review by the Audit Committee of the Board of the Company’s audited financial statements for the Performance Year, and shall be paid in the fiscal year immediately following the Performance Year. Base Salary for purposes of this Section 4(b) shall be prorated if the Term expires before the end of the calendar year to which the Annual Bonus opportunity relates. Notwithstanding the foregoing, Executive’s Annual Bonus for 2012 shall be no less than $200,000, even if the threshold performance goals established by the Board for that year are not met.

(c) Benefits. Executive shall be entitled to participate in or receive benefits under any employee benefit plan or other arrangement made available by the Company to other senior executives of the Company, on terms at least as favorable as those on which any other senior executive of the Company shall participate; provided, however, that Executive shall be entitled to no less than four weeks of paid vacation during each year during the Term, exclusive of Company holidays.

(d) Special Equity Incentive Award. As inducement for Executive to accept employment with the Company, the Company shall grant to Executive within thirty (30) days following the Agreement Date an equity incentive award relating to three million (3,000,000) shares of Company common stock. One-half of the shares relating to the equity incentive award shall be subject to time-based vesting conditions (the “Time-Based Equity Incentive”) and the remaining one-half of the shares relating to the equity incentive award shall be subject to a combination of time-based and performance-based vesting conditions (the “Performance-Based Equity Incentive”). The equity incentive award shall be subject to terms and conditions

2

(including vesting conditions) that are established by the Board (or the Compensation Committee of the Board) in its discretion, and shall be evidenced by an award agreement.

(e) Other Equity Incentives. Executive shall be eligible to participate in the Company’s long-term equity incentive plans established for its senior executives, and the Board (or the Compensation Committee of the Board) will at is discretion consider Executive for future equity incentives in a manner consistent with its evaluation of other senior executives of the Company.

5. Reimbursement of Expenses; Indemnification.

(a) Executive shall be expected to incur various reasonable business expenses customarily incurred by persons holding like positions, including but not limited to traveling, entertainment and similar expenses incurred for the benefit of the Company. The Company shall reimburse Executive for such expenses in accordance with and subject to the Company’s policies regarding business expense reimbursement, as they may exist from time to time.

(b) Within ten (10) days following Executive’s submission to the Company of an accounting for the reasonable legal expenses incurred by Executive in connection with negotiating this Agreement, the Company shall make a lump sum payment to Executive to reimburse him for such expenses, subject to a maximum reimbursement of $30,000.

(c) The Company shall indemnify and hold Executive harmless for acts and omissions in Executive’s capacity as an officer, director or employee of the Company to the maximum extent permitted under applicable law; provided, however, that neither the Company, nor any of its subsidiaries or affiliates shall indemnify Executive for any losses incurred by Employee as a result of acts that would constitute Cause (as defined in Section 6(c)).

6. Termination of Agreement. Executive’s employment under this Agreement may be terminated prior to the end of the Term by the Company or by Executive, as applicable, without any breach of this Agreement only under the following circumstances:

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

(b) Disability. If Executive becomes Disabled during the Term, the Company may terminate Executive’s employment for “Disability”. In such event, Executive’s employment with the Company shall terminate effective on the 30th day the after the Company provides Executive with notice of termination. For purposes of this Agreement, “Disabled” means a condition, resulting from bodily injury or disease, that renders, and for a six consecutive month period has rendered, Executive unable to perform substantially the duties pertaining to his employment with the Company. A return to work of less than fourteen (14) consecutive days will not be considered an interruption in Employee’s six consecutive months of Disability. Disability will be determined by the Company on the basis of medical evidence satisfactory to the Company.

3

(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 a material bad faith act of fraud, embezzlement, misappropriation, willful misconduct, gross negligence, or breach of fiduciary duty, in each case against the Company.

(d) Resignation for Good Reason. Executive may resign from his employment for Good Reason. For purposes of this Agreement, “Good Reason” means the occurrence of any of the following events, unless Executive otherwise consents in writing to such event: (i) a material diminution in Executive’s authority, duties or responsibilities (including Executive no longer reporting directly to the Board); (ii) a material reduction in Executive’s Base Salary; (iii) requiring Executive to relocate his place of employment more than 50 miles from Charlotte, North Carolina (but not including any relocation that relates to a change in the Company’s principal executive offices); or (iv) a material violation by the Company of this Agreement. Executive shall provide the Company with a written notice of resignation within ninety (90) days following the occurrence of the event constituting Good Reason and the Company shall have a period of thirty (30) days following its receipt of such notice in which to cure such event without such event constituting Good Reason. If the Company does not cure the condition or conditions by the end of such thirty (30) day period, Executive may voluntarily terminate employment within thirty (30) days after the last day of the thirty (30) day cure period. Executive’s voluntary termination of employment other than in accordance with the requirements of this Section 6(d) shall not constitute resignation for Good Reason.

(e) Without Cause. The Company may terminate Executive’s employment under this Agreement without Cause upon thirty (30) day advance notice to Executive.

(f) Resignation without Good Reason. Executive may resign his employment without Good Reason upon thirty (30) day advance notice to the Company.

(g) Expiration of the Term. The Agreement and Executive’s employment under this Agreement shall automatically terminate on the last day of the Term, as determined pursuant to Section 2 (subject to Section 7(d)).

4

Any termination of Executive’s employment hereunder by the Company or Executive (other than by reason of Executive’s death) shall be communicated by a notice of termination to the other party to this Agreement. For purposes of this Agreement, a “notice of termination” means a written notice which (i) indicates the specific provision of the Agreement relied upon for the termination, (ii) sets forth in reasonable detail any facts and circumstances claimed to provide a basis for termination of the Executive’s employment under the specified Agreement provision and (iii) specifies the effective date of the termination. Any notice of termination shall be delivered in accordance with the notice procedures prescribed in Section 13.

7. Termination Payments and Benefits.

(a) Termination by Death or Disability. Upon the termination of Executive’s employment by reason of his death or Disability, the Company shall pay to Executive (or to the personal representatives of his estate) within thirty (30) days after the termination of employment date a lump sum amount equal to the sum of Executive’s earned but unpaid Base Salary, Annual Bonus and other compensation as of the date of termination; his accrued vacation; and any accrued but unreimbursed expenses required to be reimbursed under this Agreement (the “Accrued Amounts”), and the Company shall provide to Executive any vested benefits or entitlements under any applicable Company benefit or compensation plan, program, policy or arrangement (the “Vested Benefits”). In addition, (i) all of Executive’s unvested Time-Based Equity Incentive (and any other unvested stock incentive awards held by Executive that vest solely on account of the passage of time) will become immediately vested, payable and exercisable, (ii) contingent upon the level of performance goal attainment for the Performance Year ending within the calendar year in which Executive’s employment terminates, Executive shall vest in a pro-rata portion of the Performance-Based Equity Incentive in which the Executive would have become vested had his employment not terminated during that calendar year, and (iii) contingent upon the level of performance goal attainment for the Performance Year ending within the calendar year in which Executive’s employment terminates, Executive shall be paid in a single lump sum a pro-rata portion of the Annual Bonus that Executive would have earned had his employment not terminated during that calendar year. For purposes of clauses (ii) and (iii) above, the pro-ration shall be determined based on the number of days that have elapsed from the first day of the calendar year to Executive’s termination of employment date. The lump-sum pro-rata Annual Bonus payment (described in clause (iii) above), if any, shall be paid by the Company to Executive within thirty (30) days following the final review by the Audit Committee of the Board of the Company’s audited financial statements for the Performance Year, and shall be paid in the fiscal year immediately following the Performance Year.

(b) Termination by the Company for Cause; Resignation by Executive without Good Reason; Expiration of the Term. Upon the termination of the Executive’s employment by the Company for Cause or by resignation of the Executive without Good Reason, or upon expiration of the Agreement pursuant to Section 6(g), the Company shall pay to the Executive or to the personal representatives of his estate within thirty (30) days after the termination date a lump sum amount equal to Executive’s Accrued Amounts and shall be provided Executive’s Vested Benefits.

5

(c) Termination by the Company without Cause; Resignation by Executive for Good Reason. If before the expiration of the Term the Company terminates Executive’s employment other than for Cause or Executive resigns for Good Reason, Executive shall be entitled to receive from the Company a lump sum cash payment within thirty (30) days after the termination date equal to Executive’s Accrued Amounts, and his Vested Benefits shall be paid or provided in accordance with the terms of any applicable employee benefit plans. In addition, Executive will be entitled to (i) receive continued payment of Executive’s then current Base Salary in accordance with the Company’s standard payroll practices for the period beginning on the termination date and ending on the 18-month anniversary of the termination date (the “Severance Period”); (ii) continue participation for himself and his covered dependents in the Company’s medical and dental benefit plans during the Severance Period at the same premium amount charged to active employees during such period (provided, such medical and dental benefit plan coverage shall cease on the date Executive becomes eligible for coverage under any medical plan provided by any subsequent employer or pursuant to a consulting arrangement); (iii) immediate vesting of a pro-rata portion of the unvested Time-Based Equity Incentive (and any other unvested stock incentive awards held by Executive that vest solely on account of the passage of time) that would have vested on December 31 of the year in which termination occurs had Executive’s employment not terminated; (iv) contingent upon the level of performance goal attainment for the Performance Year ending within the calendar year in which Executive’s employment terminates, vest in a pro-rata portion of the Performance-Based Equity Incentive in which the Executive would have become vested had his employment not terminated during that calendar year, and (v) contingent upon the level of performance goal attainment for the Performance Year ending within the calendar year in which Executive’s employment terminates, receive a lump sum payment equal to a pro-rata portion of the Annual Bonus that Executive would have earned had his employment not terminated during that calendar year. For purposes of clauses (iii), (iv) and (v) above, the pro-ration shall be determined based on the number of days that have elapsed from the first day of the calendar year to Executive’s termination of employment date. Executive’s rights to the severance payments and benefits described in clauses (i) through (v) above are expressly conditioned on Executive having executed and delivered to the Company (no later than the 50th day following the date on which his employment terminated) and having not revoked, a general release of the Company and its affiliates substantially in the form attached hereto as Appendix A and Executive’s compliance with the requirements of Section 9. The salary continuation payments described in (i) above shall begin to be paid on the sixtieth (60th) day following the date on which Executive’s employment terminated (or such later date as may be required by Section 21(b)(ii)) (the “Severance Commencement Date”), and the first payment shall include all of the Base Salary payments that would otherwise have been paid during the period starting on the employment termination date and ending on the Severance Commencement Date. The lump-sum severance payment, if any, corresponding to Executive’s pro-rata Annual Bonus (described in clause (v) above), shall be paid by the Company to Executive within thirty (30) days following the final review by the Audit Committee of the Board of the Company’s audited financial statements for such Performance Year, and shall be paid in the fiscal year immediately following the Performance Year.

(d) Survival. Neither the termination of the Executive’s employment hereunder nor the expiration of the Term shall impair the rights or obligations of any party hereto that have

6

accrued hereunder prior to such termination or expiration. The obligations of Section 9 shall, to the extent provided, survive the termination or expiration of the Executive’s employment with the Company and, as applicable, shall be fully enforceable thereafter in accordance with the terms of this Agreement.

(e) Mitigation of Damages. In the event of any termination of the Executive’s employment, the Executive shall not be required to seek other employment to mitigate damages, and any income earned by the Executive from other employment or self-employment shall not be offset against any obligations of the Company to Executive under this Agreement.

8. Change of Control Payments and Benefits.

(a) Upon the occurrence of a Change of Control (as defined below), all of Executive’s unvested Time-Based Equity Incentive (and any other unvested stock incentive awards held by Executive that are scheduled to vest solely on account of the passage of time) and unvested Performance-Based Equity Incentive will become immediately vested, payable and exercisable at the time of the Change of Control.

(b) If, within six (6) months following the occurrence of a Change of Control, Executive’s employment is terminated by the Company without Cause or Executive resigns for Good Reason, in addition to the payments and benefits described in clauses (i) through (iv) of Section 7(c) above, but in lieu of the payment described in clause (v) of Section 7(c), Executive shall be entitled to receive a lump sum payment equal to the pro-rata Annual Bonus that would have been payable to Executive for achievement of the target level of performance goals for the Performance Year in which termination of his employment occurs (with the pro-ration determined based on the number of days that have elapsed during the year up to the termination of employment date). Executive’s rights to the severance payment described above is expressly conditioned on Executive having executed and delivered to the Company (no later than the 50th day following the date on which his employment terminated) and having not revoked, a general release of the Company and its affiliates substantially in the form attached hereto as Appendix A and Executive’s compliance with the requirements of Section 9. The lump sum pro-rated Annual Bonus payment shall be paid on the Severance Commencement Date.

(c) For purposes of this Agreement, “Change of Control” shall have the same meaning as assigned to that term in the Company’s 2009 Incentive Compensation Plan.

(d) Notwithstanding any other provisions of this Agreement, in the event that any payment, benefit, property or right received or to be received by Executive in connection with a Change of Control or Executive’s termination of employment in respect of a Change of Control (whether pursuant to the terms of this Agreement or any other plan, arrangement or agreement with the Company) (collectively, the “Total Payments”) would be subject (in whole or part) to the tax imposed by Section 4999 of the Internal Revenue Code of 1986, as amended or any successor provision (the “Excise Tax”), then the payments and benefits provided under this Agreement that are subject to the Excise Tax (the “Parachute Payments”) and which are payable in cash shall first be reduced, and the noncash Parachute Payments shall thereafter be reduced, to

7

the extent necessary so that no portion of the Total Payments is subject to the Excise Tax, but only if (1) the net amount of such Total Payments, as so reduced (and after subtracting the net amount of federal, state and local income taxes on such reduced Total Payments) is greater than or equal to (2) the net amount of such Total Payment without such reduction (but after subtracting the net amount of federal, state and local income taxes on such Total Payments and the amount of Excise Tax to which the Executive would be subject in respect of such unreduced Total Payments).

9. Restrictive Covenants.

(a) Non-Competition. While Executive is employed, and for a period of eighteen (18) months following the date of termination of his employment for any reason (other than on account of non-renewal or non-extension of the Term) Executive 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.

(b) Confidential Information. Executive 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) concerning the business, customers, clients, contacts, prospects, and assets of the Company and the Related Entities 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 Executive 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 Executive’s part. Executive 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 Executive 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, or otherwise prohibited under this section. Notwithstanding the foregoing, Executive may disclose Confidential Information (i) that he is required by subpoena to disclose (provided that Executive furnishes the Company with prompt written notice of receipt of such subpoena), or (ii) with the prior written consent of the Company. Executive will deliver promptly to the Company, at the termination of his employment or at any other time at the Company’s request, without retaining any copies (other than Executive Records, as defined below), all documents and other materials in his possession relating, directly or indirectly, to any Confidential Information (subject to the last

8

sentence in Section 9(e) below). For purposes of this Agreement, “Executive Records” shall mean any written or electronic records of Executive’s business and personal contacts.

(c) Non-Solicitation of Employees. While Executive is employed, and for a period of eighteen (18) months following the date of termination of his employment for any reason including non-renewal or non-extension of the Term (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, 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 9(c) for Executive 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 former employee or from a third party, and providing a reference setting forth Executive’s personal views about such current or former employee in connection with such request.

(d) Non-Solicitation of Business Partners. During the Restricted Period, Executive 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. Executive hereby expressly covenants and agrees that following termination of Executive’s employment with the Company for any reason or at any time upon the Company’s request, Executive 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 Executive shall be permitted to retain Executive Records.

(f) Remedies for Breach. Executive 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 Executive from committing any violation of this section, and Executive hereby consents to the issuance of such injunction.

9

10. Disputes.

(a) Except as provided in Section 9(f), 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 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.

(b) If, with respect to any alleged failure by the Company to comply with any of the terms of this Agreement, Executive hires legal counsel with respect to this Agreement or institutes any negotiations or institutes or responds to legal action to assert or defend the validity of, enforce his rights under, or recover damages for breach of this Agreement, and thereafter the Company is found in a judgment no longer subject to review or appeal to have breached this Agreement in any material respect, then the Company shall reimburse Executive for his actual expenses for attorneys’ fees and disbursements within thirty (30) days following receipt of any invoice for such expenses.

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

12. Validity. The invalidity or unenforceability of any provision or provisions of this Agreement shall not affect the validity or enforceability of any other provision of this Agreement, which shall remain in full force and effect.

13. Notices. All notices and other communications given or made pursuant to this Agreement shall be in writing and shall be deemed effectively given: (a) upon personal delivery to the party to be notified, (b) when sent by confirmed electronic mail or facsimile if sent during normal business hours of the recipient, and if not so confirmed, then on the next business day, (c) five (5) days after having been sent by registered or certified mail, return receipt requested, postage prepaid, or (d) one day after deposit with a nationally recognized overnight courier, specifying next-day delivery, with written verification of receipt. All communications shall be sent:

(a) To Executive, at:

Last address in records of Company

(b) To the Company, at:

Horizon Lines, Inc.

4064 Colony Road, Suite 200

Charlotte, North Carolina 28211

Attention: General Counsel

Telecopy: 704 ###-###-####

10

Telephone: 704 ###-###-####

or to such other address as may have been furnished by a party hereto to the other parties hereto, by like notice. For purposes of this Agreement, the term “business day” means any day other than a Saturday or a Sunday or a day on which commercial banking institutions in the City of Charlotte, State of North Carolina, are authorized by law to be closed.

14. Counterparts. This Agreement may be executed in several counterparts, each of which shall be deemed to be an original, but all of which together will constitute one and the same Agreement.

15. Entire Agreement. The terms of this Agreement are intended by the parties to be the final expression of their agreement with respect to the employment of Executive by the Company and may not be contradicted by evidence of any prior or contemporaneous agreement. The parties further intend that this Agreement shall constitute the complete and exclusive statement of its terms and that no extrinsic evidence whatsoever may be introduced in any judicial, administrative, or other legal proceeding to vary the terms of this Agreement. This Agreement terminates and supersedes any and all prior agreements and understandings (whether written or oral) between the parties with respect to the subject matter of this Agreement. Executive acknowledges and agrees that neither the Company nor anyone acting on its behalf has made, and is not making, and in executing this Agreement, Executive has not relied upon, any representations, promises or inducements except to the extent the same is expressly set forth in this Agreement.

16. Amendments; Waivers. This Agreement contains the entire agreement of the parties with respect to the employment of Executive by the Company. No amendment or modification of this Agreement shall be valid unless evidenced by a written instrument executed by the parties hereto. No waiver by either party of any breach by the other party of any provision or conditions of this Agreement shall be deemed a waiver of any similar or dissimilar provision or condition at the same or any prior or subsequent time.

17. Disparagement. From the Agreement Date forward, Executive shall not make, and shall not cause or direct any person or entity to make, any disparaging or untrue comments or statements, whether written or oral, about the Company or any Related Entity (or any shareholder, member, director, manager or officer thereof). From the Agreement Date forward, the Company and any Related Entity shall not make, and shall not cause or direct any person or entity to make, any disparaging or untrue comments or statements, whether written or oral, about Executive. “Disparaging” comments or statements include such comments or statements which discredit, ridicule, or defame any person or entity or place such person or entity in a negative light or impair the reputation, goodwill or commercial interest thereof. Notwithstanding the foregoing, it shall not be a violation of this Section 17 for either party to make any statements necessary to enforce this Agreement, or to testify truthfully under oath pursuant to any lawful court order or subpoena or otherwise provide disclosures required by law.

18. Transferability. The rights, benefits and obligations of the Company under this Agreement shall not be transferable other than to successors or assigns of the Company in

11

connection with a corporate transaction, and all covenants and agreements hereunder shall inure to the benefit of and be enforceable by or against, any such successors and assigns. Whenever the term “Company” is used in this Agreement, such term shall mean and include the Company and its successors and assigns. The rights and benefits of Executive under this Agreement shall not be transferable other than rights to property or compensation that may pass on his death to his estate or beneficiaries through his will or the laws of descent and distribution and the terms of any Company compensation or benefit plan.

19. Severability. If any provision of this Agreement or the application thereof is held invalid or unenforceable, the invalidity or unenforceability thereof shall not affect any other provisions of this Agreement which can be given effect without the invalid or unenforceable provision, and to this end the provisions of this Agreement are to be severable.

20. Tax Withholding. The Company may withhold from any payments due to Executive hereunder such amounts as it determines are required to be withheld under applicable federal, state and local tax laws.

21. Section 409A.

(a) The parties acknowledge and agree that, to the extent applicable, this Agreement shall be interpreted in accordance with Section 409A of the Internal Revenue Code of 1986, as amended, and the Department of Treasury Regulations and other interpretive guidance promulgated thereunder, including without limitation any such regulations or other guidance that may be issued after the Agreement Date (collectively, “Section 409A”). Notwithstanding any provision of this Agreement to the contrary, in the event that the Company determines that any compensation or benefits payable or provided under this Agreement may be subject to Section 409A, the Company may adopt (without any obligation to do so or to indemnify the Executive for failure to do so) such limited amendments to this Agreement and appropriate policies and procedures, including amendments and policies with retroactive effect, that the Company reasonably determines are necessary or appropriate to (i) exempt the compensation and benefits payable under this Agreement from Section 409A and/or preserve the intended tax treatment of the compensation and benefits provided with respect to this Agreement or (ii) comply with the requirements of Section 409A. No provision of this Agreement shall be interpreted or construed to transfer any liability for failure to comply with the requirements of Section 409A from Executive or any other individual to the Company or any of their respective affiliates, employees or agents.

(b) Notwithstanding any provision to the contrary in this Agreement:

(i) No amount payable on account of Executive’s termination of employment shall be paid unless the termination of Executive’s employment constitutes a “separation from service” within the meaning of Section 409A.

(ii) If Executive is deemed at the time of his separation from service to be a “specified employee” for purposes of Section 409A(a)(2)(B)(i) of the Internal Revenue Code of 1986, as amended (the “Code”), to the extent delayed commencement (any such delayed

12

commencement, a “Payment Delay”) of any portion of the termination benefits to which Executive is entitled under this Agreement is required in order to avoid a prohibited distribution under Section 409A(a)(2)(B)(i) of the Code, such portion of Executive’s termination benefits shall not be provided to Executive prior to the earlier of (A) the expiration of the six-month period measured from the date of Executive’s “separation from service” with the Company (as such term is defined under Section 409A) or (B) the date of Executive’s death. Upon the earlier of such dates (the “Delayed Payment Date”), all payments deferred pursuant to this Section 21(b)(ii) shall be paid in a lump sum to Executive, and any remaining payments due under the Agreement shall be paid as otherwise provided herein.

(iii) The determination of whether Executive is a “specified employee” for purposes of Section 409A(a)(2)(B)(i) of the Code as of the time of his separation from service shall be made by the Company in accordance with Section 409A.

(iv) For purposes of Section 409A, Executive’s right to receive installment payments shall be treated as a right to receive a series of separate and distinct payments.

(v) The reimbursements of expenses and provision of in-kind benefits under this Agreement shall comply with the requirements of Section 409A (to the extent subject to Section 409A), which generally require (A) that the amount of expenses eligible for reimbursement, or in-kind benefits provided, during a calendar year may not affect the expenses eligible for reimbursement, or in-kind benefits to be provided, in any other taxable year; (B) the reimbursement of an eligible expense is made on or before the last day of the calendar year following the calendar year in which the expense was incurred; and (C) the right to reimbursement or in-kind benefits is not subject to liquidation or exchange for another benefit.

[signature page follows]

13

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

14

APPENDIX A

FORM OF RELEASE

In return for payment of severance benefits pursuant to my employment agreement with Horizon Lines, Inc. dated [            ] (the “Employment Agreement”), I hereby generally and completely release Horizon Lines, Inc. (“Horizon Lines”), its parent and subsidiary entities (collectively the “Company”), and its or their directors, officers, employees, shareholders, partners, agents, attorneys, predecessors, successors, insurers, affiliates, and assigns (collectively “Released Parties”), from any and all claims, liabilities and obligations, both known and unknown, that arise out of or are in any way related to events, acts, conduct, or omissions occurring prior to my signing this Release. This general release includes, but is not limited to: (1) all claims arising out of or in any way related to my employment with the Company or the termination of that employment; (2) all claims related to my compensation or benefits from the Company, including wages, salary, bonuses, commissions, vacation pay, expense reimbursements (to the extent permitted by applicable law), severance pay, fringe benefits, stock, stock options, or any other ownership interests in the Company; (3) all claims for breach of contract, wrongful termination, and breach of the implied covenant of good faith and fair dealing; (4) all tort claims, including without limitation claims for fraud, defamation, emotional distress, and discharge in violation of public policy; and (5) all federal, state, and local statutory claims, including without limitation claims for discrimination, harassment, retaliation, attorneys’ fees, or other claims arising under the federal Civil Rights Act of 1964 (as amended), the federal Americans with Disabilities Act of 1990, the federal Age Discrimination in Employment Act of 1967 (as amended) (“ADEA”), the federal Worker Adjustment and Retraining Notification Act (as amended) and similar laws in other jurisdictions, the Employee Retirement Income Security Act of 1974 (as amended), the Family and Medical Leave Act of 1993, and any similar laws in other jurisdictions; provided, however, that this Release does not waive, release or otherwise discharge any claim or cause of action arising after the date I sign this Release.

This Release includes a release of claims of discrimination or retaliation on the basis of workers’ compensation status, but does not include workers’ compensation claims. Excluded from this Release are any claims which by law cannot be waived in a private agreement between employer and employee, including but not limited to the right to file a charge with or participate in an investigation conducted by the Equal Employment Opportunity Commission (“EEOC”) or any state or local fair employment practices agency. I waive, however, any right to any monetary recovery or other relief should the EEOC or any other agency pursue a claim on my behalf.

I acknowledge and represent that I have not suffered any age or other discrimination, harassment, retaliation, or wrongful treatment by any Released Party. I also acknowledge and represent that I have not been denied any rights including, but not limited to, rights to a leave or reinstatement from a leave under the Family and Medical Leave Act of 1993, the Uniformed Services Employment and Reemployment Rights Act of 1994, or any similar law of any jurisdiction.

15

I agree that I am voluntarily executing this Release. I acknowledge that I am knowingly and voluntarily waiving and releasing any rights I may have under the ADEA, as amended by the Older Workers Benefit Protection Act of 1990, and that the consideration given for this Release is in addition to anything of value to which I was already entitled. I further acknowledge that I have been advised by this writing, as required by the ADEA, that: (a) my waiver and release specified in this paragraph does not apply to any rights or claims that may arise after the date I sign this Release; (b) I have been advised to consult with an attorney prior to signing this Release; (c) if my employment termination involves an employment termination program, I have received a disclosure from the Company that includes a description of the class, unit or group of individuals covered by the program, the eligibility factors for such program, and any time limits applicable to such program and a list of job titles and ages of all employees selected for this group termination and ages of those individuals in the same job classification or organizational unit who were not selected for termination; (d) I have at least twenty-one (21) or forty-five (45) days, depending on the circumstances of my employment termination, from the date that I receive this Release (although I may choose to sign it any time on or after my employment termination date) to consider the release; (e) I have seven (7) calendar days after I sign this Release to revoke it (“Revocation Period”) by sending my revocation to the Vice President of Human Resources in writing at 4064 Colony Road, Suite 200, Charlotte, North Carolina 28211; fax ###-###-####; and (f) this Release will not be effective until I have signed it and returned it to the Company’s Corporate Secretary and the Revocation Period has expired (the “Effective Date” ).

I UNDERSTAND THAT THIS RELEASE AGREEMENT INCLUDES A RELEASE OF ALL KNOWN AND UNKNOWN CLAIMS.

16

EXHIBIT A

BOARD MEMBERSHIPS

As of the Agreement Date, Executive is a member of the following corporate, civic or charitable boards:

None

\39647180.3

17