UNITED STATES

SECURITIES AND EXCHANGE COMMISSION

Washington, D.C. 20549

FORM 8-K

CURRENT REPORT

Pursuant to Section 13 or 15(d) of the

Securities Exchange Act of 1934

Date of Report (Date of earliest event reported): July 5, 2012

HORIZON LINES, INC.

(Exact name of registrant as specified in its Charter)

4064 Colony Road, Suite 200

Charlotte, North Carolina 28211

(Address of Principal Executive Offices, including Zip Code)

(704) 973-7000

(Registrant’s telephone number, including area code)

N/A

(Former Name or Former Address, if Changed Since Last Report)

Check the appropriate box below if the Form 8-K filing is intended to simultaneously satisfy the filing obligation of the registrant under any of the following provisions:

Item 5.02. Departure of Directors or Certain Officers; Election of Directors; Appointment of Certain Officers; Compensatory Arrangements of Certain Officers.

Election of Director; Appointment of Officer; Compensatory Arrangement for Officer

On July 5, 2012, the Board of Directors (the “Board”) of Horizon Lines, Inc. (the “Company”) granted Samuel A. Woodward, the Company’s President and Chief Executive Officer, 3,000,000 restricted stock units (“RSUs”). The grant was made pursuant to the employment agreement between Mr. Woodward and the Company. One half (1,500,000) of the RSUs will vest on the following dates if Mr. Woodward remains in continuous employment with the Company: 250,000 RSUs on December 31, 2012, 500,000 RSUs on December 31, 2013, 500,000 RSUs on December 31, 2014, and 250,000 RSUs on June 30, 2015. The other half (1,500,000) of the RSUs will vest on the following dates if Mr. Woodward remains in continuous employment with the Company and certain performance goals established by the Board or the Compensation Committee have been met: 250,000 RSUs on December 31, 2012, 625,000 RSUs on December 21, 2013, and 625,000 RSUs on December 31, 2014. If any of the performance based RSUs do not vest on their assigned performance date solely because the performance goals are not met, then such RSUs shall remain outstanding and shall be eligible to vest on subsequent performance dates to the extent performance goals are established and met for such subsequent year. All of the RSUs carry dividend equivalent rights.

If Mr. Woodward’s employment is terminated as a result of his death or disability, Mr. Woodward’s time-based RSUs will immediately vest and become payable, and Mr. Woodward’s performance based RSUs will pro-ratably vest for the year in which his employment terminates, contingent upon performance goal achievement for that year.

If Mr. Woodward’s employment is terminated by the Company without cause or if he terminates his employment for good reason (as those terms are defined in his employment agreement), a pro-rata portion of Mr. Woodward’s unvested, time-based RSUs that would have vested at the end of the year of the termination will immediately vest and become payable, and Mr. Woodward’s performance based RSUs will pro-ratably vest for the year in which his employment terminates, contingent upon performance goal achievement for that year. In the event of a change of control of the Company, all of Mr. Woodward’s unvested time-based RSUs and his unvested performance based RSUs will vest immediately and be paid at the time of the change of control.

SIGNATURES

Pursuant to the requirements of the Securities Exchange Act of 1934, the registrant has duly caused this report to be signed on its behalf by the undersigned hereunto duly authorized.