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): February 17, 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.

On February 17, 2012 the Board of Directors of Horizon Lines, Inc. (the “Company”) approved a bonus plan and a management incentive plan. Three of the Company’s named executive officers, as well as certain other employees, participate in the two plans.

In connection with the bonus plan, the Company will pay $100,000 to each of Michael T. Avara, the Executive Vice President and Chief Financial Officer, Brian Taylor, the Executive Vice President and Chief Operating Officer and Michael F. Zendan II, the Senior Vice President, General Counsel and Secretary by February 29, 2012.

The management incentive plan provides an additional opportunity for Mr. Avara, Mr. Taylor and Mr. Zendan, if a Company financial performance target and certain business goals are met during 2012. The financial performance target is based on the Company’s Adjusted EBITDA for 2012, which is a non-GAAP financial measure defined as net income plus net interest expense, income taxes, depreciation and amortization, and excludes certain expenses and costs related to the antitrust matters and related lawsuits, as well as severance, restructuring and impairment charges. Attainment of the business goals will be determined by the Compensation Committee of the Board of Directors.

The management incentive plan target incentive award for each of Mr. Avara, Mr. Taylor and Mr. Zendan is $100,000. Sixty percent (60%) of this amount will be paid if the Adjusted EBITDA target is met, as measured at the end of 2012. Forty percent (40%) of this amount will be paid if and when the business goals are met during 2012. Consequently, plan participants will receive payment of their full target incentive award only if both the Adjusted EBITDA target and the business goals are met. No additional bonus over the amount of the target incentive award is payable for exceeding either the Adjusted EBITDA target or the business goals. Generally, a named executive officer must be employed by the Company on the date of payment to receive any portion of his target incentive award under the plan.

On February 21, 2012, the Board of Directors authorized the Company to enter into an indemnification agreement with Mr. Zendan. The Board of Directors also authorized the Company to enter into new indemnification agreements to replace the current indemnification agreements of Mr. Avara and Mr. Taylor. The indemnification agreements are considered to be important employee benefit arrangements for the officers of the Company. The prior indemnification agreements of Mr. Avara and Mr. Taylor have been updated to reflect the current organizational structure of the Company.

A form of the indemnification agreements is attached hereto as Exhibit 10.1 and is incorporated by reference herein in its entirety. The indemnification agreement requires the Company to indemnify and hold harmless each officer to the fullest extent permitted under Delaware law against all expenses, judgments, penalties, fines and amounts paid in settlement relating to any proceedings or claims in connection with such officer’s capacity, office or position with the Company. In addition, the indemnification agreement requires the Company to advance expenses incurred by or on behalf of such officer in connection with any such proceeding or claim, subject to the terms and conditions provided in the agreement.

Item 9.01 Financial Statements and 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

Item 9.01 Financial Statements and Exhibits.