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 25, 2012

HORIZON LINES, INC.

(Exact name of registrant as specified in its Charter)

(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

Change of Control Severance Agreement

On July 25, 2012, the Board of Directors (the “Board”) of Horizon Lines, Inc. (the “Company”) authorized the Company to enter into a Change of Control Severance Agreement, dated July 25, 2012 (the “COC Agreement”) with Michael T. Avara, Executive Vice President and Chief Financial Officer, Brian W. Taylor, Executive Vice President and Chief Operating Officer and Michael F. Zendan II, Senior Vice President, General Counsel and Secretary and certain other officers of the Company. The principal executive officer did not enter into a COC Agreement with the Company, but he has an employment agreement with the Company that includes change of control terms.

The COC Agreements provide that if the executive is terminated without “Cause”, or if the executive terminates his employment for “Good Reason”, within 24 months of a “Change of Control” (as those terms are defined in the COC Agreement), the executive will be entitled to receive:

The executive shall be eligible to receive the payments and benefits under the COC Agreement if the executive executes a release in favor of the Company and enters into a noncompete, nonsolicitation and nondisclosure agreement in favor of the Company.

If the payments or benefits received by any executive under the COC Agreement and any other compensation arrangement would be subject to the tax imposed by Section 4999 of the Internal Revenue Code, then the payments and benefits the executive is entitled to under the COC Agreement will be reduced such that no portion of the total payments the executive will receive under the COC Agreement and any other arrangement are subject to the excise tax, but only if the net amount of such reduced payments after taxes is greater than or equal to the net amount after taxes of such payments without such reduction.

The term of each COC Agreement will end on December 31, 2013, and shall automatically be extended for additional one-year periods, unless 90 days prior to the end of the term, the Company or the executive shall give notice to the other party not to extend the term. However, the term shall immediately expire if the executive is terminated by the Company for any reason prior to a Change of Control. Further, in the event of a Change of Control, the term shall automatically be extended to the second anniversary of the Change of Control, and the term shall not end during the severance period of an executive.

Any payments an executive receives under the COC Agreement will be in lieu of any similar severance or termination compensation such that there will be no duplication of severance payments or benefits.

The foregoing summary of the COC Agreement is qualified in its entirety by reference to the full text of the COC Agreement, a form of which is filed as Exhibit 10.1 hereto and is incorporated by reference herein.

Amendment to Executive Severance Plan

On July 25, 2012, the Board authorized the Company to amend the Executive Severance Plan to provide that if an executive is a party to a COC Agreement, it will not preclude the executive from being eligible to participate in the Executive Severance Plan.

2012 Incentive Compensation Plan

On July 25, 2012, the Board adopted the 2012 Incentive Compensation Plan (the “2012 Plan”) to provide employees of the Company and its affiliates the opportunity to earn equity and other incentive compensation. The Board also reserved and authorized 4,450,000 shares of the Company’s common stock for issuance pursuant to awards to be granted under the 2012 Plan. The 2012 Plan does not replace or supersede the Company’s 2009 Incentive Compensation Plan, and approximately 35,000 shares of the Company’s common stock remain authorized and available for issuance under the 2009 plan.

The following types of awards may be granted under the 2012 Plan:

The 2012 Plan will terminate on the close of business on the day immediately following the tenth anniversary of the 2012 Plan’s effective date and no new awards may be granted after its termination. Generally, the Board may terminate the 2012 Plan at any time and may amend the 2012 Plan at any time.

The foregoing summary of the 2012 Plan is qualified in its entirety by reference to the full text of the 2012 Plan, which is filed as Exhibit 10.2 hereto and is incorporated by reference herein.

Director Restricted Stock Unit Awards

On July 25, 2012, the Board granted each non-employee member of the Board 150,000 restricted stock units pursuant to the terms of the 2012 Plan. The restricted stock units will vest on the following dates if the director is continuously a member of the Board on the following dates: 30,000 restricted stock units on March 31, 2013, 60,000 restricted stock units on March 31, 2014 and 60,000 restricted stock units on March 31, 2015. All of the restricted stock units will be settled in shares of the Company’s stock. All of the unvested restricted stock units shall immediately vest and no longer be subject to restriction immediately prior to a change of control, as defined in the 2012 Plan. All of the restricted stock units carry dividend equivalent rights.

The foregoing summary of the restricted stock units granted to directors is qualified in its entirety by reference to the full text of the form of the Restricted Stock Unit Agreement, which is filed as Exhibit 10.3 hereto and is incorporated by reference herein.

Employee Restricted Stock Unit Awards

On July 25, 2012, the Committee granted certain officers of the Company restricted stock units, subject to the terms of the 2012 Plan, including the following grants to certain executive officers: Michael T. Avara, 616,667 restricted stock units; Brian W. Taylor, 616,667 restricted stock units; and Michael F. Zendan II, 375,000 restricted stock units.

One half of the restricted stock units will vest on the following dates solely if such executive remains in continuous employment with the Company: 61,668 restricted stock units for Mr. Avara and Mr. Taylor and 37,500 restricted stock units for Mr. Zendan, on March 31, 2013; 123,333 restricted stock units for Mr. Avara and Mr. Taylor and 75,000 restricted stock units for Mr. Zendan, on March 31, 2014; and 123,333 restricted stock units for Mr. Avara and Mr. Taylor and 75,000 restricted stock units for Mr. Zendan, on March 31, 2015.

The other half of the restricted stock units will vest on the following dates if such executive remains in continuous employment with the Company and certain performance goals established by the Committee have been met: 61,667 restricted stock units for Mr. Avara and Mr. Taylor and 37,500 restricted stock units for Mr. Zendan, on March 31, 2013; 123,333 restricted stock units for Mr. Avara and Mr. Taylor and 75,000 restricted stock units for Mr. Zendan, on March 31, 2014; and 123,333 restricted stock units for Mr. Avara and Mr. Taylor and 75,000 restricted stock units for Mr. Zendan, on March 31, 2015. If any of the performance based restricted stock

units do not vest on their assigned performance date solely because the performance goals are not met, then such restricted stock units shall remain outstanding and be eligible to vest on subsequent vesting dates to the extent the Company achieves the performance goals for such subsequent performance period.

One half of any vested restricted stock units will be settled in shares of the Company’s stock, and the Committee has the discretion to settle the other half of any vested restricted stock in either shares of the Company’s stock, cash or both. All of the unvested restricted stock units shall immediately vest and no longer be subject to restriction immediately prior to a change of control, as defined in the 2012 Plan. All of the restricted stock units carry dividend equivalent rights.

The foregoing summary of the restricted stock units granted to officers is qualified in its entirety by reference to the full text of the form of the Restricted Stock Unit Agreement, which is filed as Exhibit 10.4 hereto and is incorporated by reference herein.

Item 9.01 Financial Statements and Exhibits.

(d) Exhibits

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.

Exhibit Index