Exhibit 10.1

RESTRICTED STOCK UNIT AGREEMENT

RESTRICTED STOCK UNIT AGREEMENT (this “Agreement”), dated as of July 5, 2012 (the “Grant Date”), by and between the Samuel A. Woodward (the “Executive”) and Horizon Lines, Inc. (the “Company”).

W I T N E S S E T H:

WHEREAS, the Company and the Executive have entered into an employment agreement, dated June 7, 2012 (the “Employment Agreement”);

WHEREAS, pursuant to the terms of the Employment Agreement, the Company has agreed to grant to the Executive an equity incentive award relating to three million (3,000,000) shares of common stock of the Company, which is to be subject to a combination of time-based and performance-based vesting conditions; and

WHEREAS, the Company’s Board of Directors (the “Board”) has determined that it is desirable to grant such equity incentive award in the form of restricted stock units.

NOW, THEREFORE, the parties agree as follows:

1. Grant of Restricted Stock Units. Pursuant to the provisions of this Restricted Stock Unit Agreement (the “Agreement”), the Company hereby grants to the Executive three million (3,000,000) restricted stock units (the “RSUs”). Each RSU shall entitle the Executive to receive one share of common stock of the Company (“Common Stock”), and cash equal to the amount of any dividend equivalents credited to such RSU, subject to and in accordance with the terms and conditions specified in this Agreement. All capitalized terms used in this Agreement, to the extent not defined, shall have the same meanings as assigned to those terms in the Employment Agreement.

2. Vesting. The RSUs shall vest and cease to be subject to any restrictions in accordance with the provisions of this Section 2.

(a) Time-Based RSUs. One-million five hundred thousand (1,500,000) RSUs shall be “Time-Based RSUs” and shall vest in accordance with the following schedule:

(i) 250,000 RSUs will vest if the Executive remains in continuous employment with the Company from the Grant Date to December 31, 2012;

(ii) 500,000 RSUs will vest if the Executive remains in continuous employment with the Company from the Grant Date to December 31, 2013;

(iii) 500,000 RSUs will vest if the Executive remains in continuous employment with the Company from the Grant Date to December 31, 2014; and

(iv) 250,000 RSUs will vest if the Executive remains in continuous employment with the Company from the Grant Date to June 30, 2015.

Except as specifically provided in this Agreement and the Employment Agreement, unvested Time-Based RSUs shall be forfeited upon Executive’s termination of employment.

(b) Performance-Based RSUs. The remaining one-million five hundred thousand (1,500,000) RSUs shall be “Performance-Based RSUs” and shall vest on the dates set forth below (each, a “Performance Vesting Date”) in accordance with the following schedule:

(i) 250,000 RSUs will vest on December 31, 2012 if the Executive remains in continuous employment with the Company from the Grant Date to that date and the performance goals established by the Board (or the Compensation Committee of the Board (the “Committee”)) for the Company’s fiscal year ending in 2012 (the “2012 Performance Year”) are fully achieved;

(ii) 625,000 RSUs will vest on December 31, 2013 if the Executive remains in continuous employment with the Company from the Grant Date to that date and the performance goals established by the Board (or the Committee) for the Company’s fiscal year ending in 2013 (the “2013 Performance Year”) are fully achieved; and

(iii) 625,000 RSUs will vest on December 31, 2014 if the Executive remains in continuous employment with the Company from the Grant Date to that date and the performance goals established by the Board (or the Committee) for the Company’s fiscal year ending in 2014 (the “2014 Performance Year”) are fully achieved.

The Board (or the Committee) shall in its sole discretion establish the performance goals for a fiscal year (a “Performance Year”), and also may provide for vesting of less than the full number of RSUs eligible to vest for such Performance Year based on lower levels of performance goal achievement for that Performance Year. The Board (or the Committee) shall establish the performance goals for the 2013 Performance Year and the 2014 Performance Year as soon as practicable following the first day of each such Performance Year, and shall establish the performance goals for the 2012 Performance Year by no later than the Grant Date. The Board (or the Committee) shall determine the number of RSUs that have vested for a particular Performance Year after the Audit Committee of the Board has completed its final review of the Company’s audited financial statement for such Performance Year.

2

Notwithstanding the vesting schedule described above, if any Performance-Based RSUs do not vest on their assigned Performance Vesting Date solely because the performance goals for the Performance Year were not fully achieved, such Performance-Based RSUs will not be forfeited, but will remain outstanding and shall be eligible to vest on any following Performance Vesting Date (each, a “Following Vesting Date”) if the Executive remains in continuous employment with the Company to the Following Vesting Date and to the extent that the performance goals established by the Board (or the Committee) for the Performance Year ending with or immediately before the Following Vesting Date are achieved.

Except as otherwise specifically provided in this Agreement and the Employment Agreement, unvested Performance-Based RSUs shall be forfeited upon the Executive’s termination of employment; provided, however, that if the Executive’s employment terminates after the end of a Performance Year but before the Board (or the Committee) has determined the extent to which the performance goals for such Performance Year have been met, unvested Performance-Based RSUs shall not be forfeited until the Board (or the Committee) has made its determination of performance goal achievement for that Performance Year. In addition, the Executive shall forfeit all remaining unvested Performance-Based RSUs that do not vest based on the achievement of the performance goals for the 2014 Performance Year.

(c) Additional Vesting Events. Notwithstanding the foregoing, the Time-Based RSUs and the Performance-Based RSUs shall be subject to the additional vesting provisions described below:

(i) Upon the Company’s termination of the Executive’s employment without Cause or the Executive’s resignation for Good Reason, the Executive shall immediately become vested in a pro-rata number of the outstanding and unvested Time-Based RSUs that would have vested on December 31 of the calendar year in which such termination of employment occurs as if the Executive’s employment had not terminated.

(ii) Upon the Company’s termination of the Executive’s employment by the Company without Cause, on account of the Executive’s Disability or death or on account of the Executive’s resignation for Good Reason, the Performance-Based RSUs that are eligible to vest for the calendar year in which termination of employment occurs shall remain outstanding following the Executive’s termination of employment and, contingent upon the level of performance goal attainment for the Performance Year ending within such calendar year, the Executive shall vest in a pro-rata number of such Performance-Based RSUs.

3

(iii) All outstanding and unvested Time-Based RSUs shall become vested and no longer subject to restriction immediately prior to the occurrence of a Change of Control, or upon the Executive’s termination of employment due to Disability or death.

(iv) All outstanding and unvested Performance-Based RSUs shall become vested and no longer subject to restriction immediately prior to the occurrence of a Change of Control.

Any pro-ration required pursuant to this Section 2(c) shall be determined based on the number of days that have elapsed from the first day of the calendar year to the date on which the Executive’s employment terminates.

3. Settlement of RSUs.

(a) Each vested RSU shall be settled by lump sum delivery of shares of Common Stock within thirty (30) days following termination of the Executive’s employment with the Company or, if a Change of Control occurs before the Executive’s termination of employment, immediately prior to the occurrence of such Change of Control.

(b) Notwithstanding the foregoing, if the Board (or the Committee) determines pursuant to Sections 2(b) or (c)(ii) that any Performance-Based RSUs have vested after the Executive has terminated employment with the Company, then such vested RSUs shall be settled by lump sum delivery of shares of Common Stock during the Company’s fiscal year that immediately follows the Performance Year to which such vesting relates (and within no later than 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). In addition, RSUs that vest on the Executive’s termination of employment in accordance with Section 7(c) of the Employment Agreement shall be settled on the sixtieth (60th) day following the date on which Executive’s employment terminated.

(c) The lump sum delivery to the Executive shall consist of one share of Common Stock for each vested RSU and cash equal to the amount of dividend equivalents credited to the RSU (if any). The Company shall cause to be delivered to the Executive one or more unlegended, freely-transferable stock certificates in respect of the shares of Common Stock issued upon settlement of vested RSUs.

4. Dividend Equivalent Rights. The RSUs do not provide the Executive with the rights of a shareholder of Common Stock. However, the Executive shall accumulate dividend equivalent rights on all RSUs in an amount equal to the cash dividends paid with respect to a share of Common Stock on each date prior to payment of the Executive’s RSUs that a cash dividend is paid on the Company Stock. The dividend equivalent rights shall be held by the

4

Company as a bookkeeping account and shall be subject to the same terms and conditions (including vesting terms) as the corresponding RSUs and shall accumulate and be paid in the form of a single cash lump-sum payment if and when payment for the corresponding RSUs is made.

5. No Ownership. Other than the right to receive dividend equivalents, the Executive shall not have any rights of a stockholder with respect to the RSUs (including, without limitation, voting rights) until shares of Common Stock have been distributed to the Executive in connection with the Executive’s vested RSUs.

6. Nontransferability of the RSUs. The RSUs and any interest therein may not be sold, assigned, transferred, pledged, hypothecated or otherwise disposed of, except by will or the laws of descent and distribution and subject to the conditions set forth in this Agreement. Any attempt to transfer RSUs in contravention of this section is void ab initio. The RSUs shall not be subject to execution, attachment or other process.

7. Other Restrictions.

(a) The RSUs shall be subject to the terms of any compensation recoupment policy now in effect or subsequently adopted by the Board (or the Committee). The terms of any such compensation recoupment policy shall be made a part of this Agreement.

(b) The Executive acknowledges that the Executive is subject to the Company’s policies regarding compliance with securities laws (as in effect from time to time), and, pursuant to these policies, if the Executive is on the Company’s insider list, the Executive shall be required to obtain pre-clearance from the Company’s General Counsel prior to purchasing or selling any of the Company’s securities, including any shares issued upon vesting of the RSUs, and may be prohibited from selling such shares other than during an open trading window. The Executive further acknowledges that, in its discretion, the Company may prohibit the Executive from selling such shares even during an open trading window if the Company has concerns over the potential for insider trading.

8. Equitable Adjustment.

(a) The Board (or the Committee) shall equitably and proportionally adjust the number and kind of shares of Common Stock subject to the RSUs and other relevant terms set forth in this Agreement, in the event of a stock dividend, stock split or combination of shares, recapitalization or merger in which the Company is the surviving corporation, or other change in the Company’s corporate structure or capital stock (including, but not limited to, the creation or issuance to stockholders generally of rights, options or warrants for the purchase of Common Stock or preferred stock of the Company), as necessary or appropriate to preserve the intended benefits of the RSUs for the Company

5

and the Executive. For the avoidance of doubt, there shall be no adjustment solely to maintain the percentage ownership that the RSUs represent in the Company’s outstanding equity as of the Grant Date (i.e., “anti-dilution adjustment”).

(b) Notwithstanding anything in this Agreement to the contrary, the Board (or the Committee) may take the foregoing actions without the consent of the Executive, and its determination shall be conclusive and binding on all persons and for all purposes.

9. Taxes. The Executive shall be required to pay to the Company, or make arrangements satisfactory to the Company regarding the payment by the Executive to the Company of, an amount equal to all applicable payroll and other withholding taxes (which shall mean the aggregate amount of federal, state and local income and employment taxes required to be withheld in connection with the RSUs). The parties may provide for payment of applicable payroll and other withholding taxes by having the Company retain that number of shares of Common Stock (valued at their fair market value as of the date of retention) that would satisfy all or a specified portion of such taxes. No payment with respect to the RSUs granted under this Agreement shall be made until the Executive has paid or has made arrangements approved by the Company to satisfy in full all applicable payroll and other withholding taxes.

10. No Right to Continued Employment. Nothing contained in this Agreement shall be deemed to confer upon the Executive any right to continue in the employment of the Company or any affiliate. The Employment Agreement shall govern the terms of the Executive’s employment.

11. Miscellaneous.

(a) Governing Law/Jurisdiction. This Agreement shall be governed by and construed in accordance with the laws of the State of North Carolina without reference to principles of conflict of laws.

(b) Notices. Any notice required or permitted under this Agreement shall be deemed given when delivered in accordance with the notice provisions of the Employment Agreement.

(c) Failure to Enforce Not a Waiver. The failure of either party hereto to enforce at any time any provision of this Agreement shall in no way be construed to be a waiver of such provision or of any other provision hereof.

(d) Counterparts. This Agreement may be executed in two or more counterparts, each of which shall be an original but all of which together shall represent one and the same agreement.

(e) Modifications; Entire Agreement; Headings. This Agreement cannot be changed or terminated orally. This Agreement and the Employment

6

Agreement contain the entire agreement between the parties relating to the subject matter hereof. The section headings herein are intended for reference only and shall not affect the interpretation hereof.

12. Internal Revenue Code Section 409A.

(a) It is intended that any amounts payable under this Agreement shall either be exempt from or comply with Section 409A of the Code (including the Treasury regulations and other published guidance relating thereto) (“Code Section 409A”) so as not to subject the Executive to payment of any interest or additional tax imposed under Code Section 409A, and shall be consistently interpreted in accordance with such intent. To the extent that any amount payable under this Agreement would trigger the additional tax, penalty or interest imposed by Code Section 409A, this Agreement shall be modified to avoid such additional tax, penalty or interest yet preserve (to the nearest extent reasonably possible) the intended benefit payable to the Executive. 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) To the extent a payment or benefit under this Agreement is nonqualified deferred compensation subject to Code Section 409A, a termination of employment by the Executive shall not be deemed to have occurred for purposes of any provision of this Agreement providing for the payment of any amounts upon or following a termination of employment unless such termination is also a “separation from service” within the meaning of Code Section 409A and, for purposes of any such provision of this Agreement, references to a “termination,” “termination of employment” or like terms shall mean “separation from service” within the meaning of Code Section 409A. If the Executive is deemed on the date of a separation from service (within the meaning of Code Section 409A) to be a “specified employee” (within the meaning of that term under Section 409A(a)(2)(B) of the Code and determined using any identification methodology and procedure selected by the Company from time to time, or, if none, the default methodology and procedure specified under Code Section 409A), then with regard to any payment or the provision of any benefit that is “nonqualified deferred compensation” within the meaning of Code Section 409A and which is paid as a result of the Executive’s “separation from service,” such payment or benefit shall not be made or provided prior to the date which is the earlier of (A) the expiration of the six (6)-month period measured from the date of such “separation from service” of the Executive, and (B) the date of the Executive’s death (the “Delay Period”). Upon the expiration of the Delay Period, all payments and benefits delayed pursuant to this clause (whether they would have otherwise been payable in a single sum or in installments in the absence of such delay) shall be paid to the Executive in a lump sum, and any remaining payments and benefits due under this Agreement shall be paid or provided in accordance with the normal payment dates specified for them herein.

7

* * * Signature Page to Follow * * *

8

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

HORIZON LINES, INC.
By:	/s/ Jeffrey A. Brodsky
	Jeffrey A. Brodsky
	Chairman, Board of Directors
EXECUTIVE
/s/ Samuel A. Woodward
Samuel A. Woodward

9