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): June 7, 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 June 7, 2012, the Board of Directors (the “Board”) of Horizon Lines, Inc. (the “Company”) appointed Samuel A. Woodward, age 63, as President and Chief Executive Officer of the Company and as a Board member, effective on that date.

Mr. Woodward served as Managing Director of Bengur Bryan & Co. from June 2008 until May 2012. Prior to Bengur Bryan & Co., Mr. Woodward was the Chairman, President and Chief Executive Officer of Gemini Air Cargo, Inc. from March 2004 to June 2008.

On June 7, 2012, the Company entered into an employment agreement (the “Agreement”) with Mr. Woodward to serve as President and Chief Executive Officer until June 30, 2015. The Agreement will be extended for additional one year terms unless either party gives notice to the other party prior to April 1, 2015 or any subsequent anniversary thereof of its election not to extend the term. In addition, either party may terminate the Agreement upon 30 days notice.

The Agreement provides that Mr. Woodward will receive an annual base salary of $600,000, subject to periodic increases as determined by the Board. For 2012, Mr. Woodward will receive a cash bonus of no less than $200,000, even if the goals established by the Board are not met. The 2012 bonus may be up to 133% of the amount of base salary paid to Mr. Woodward during 2012 if Company financial performance meets or exceeds certain goals that the Board has established. In later years, Mr. Woodward will be eligible to receive a performance bonus of less than the 100% target and up to 133% of the amount of his annual base salary depending upon whether performance targets established by the Board or the Compensation Committee of the Board for that year have been partially met, met, or exceeded.

Mr. Woodward will also receive 3,000,000 equity incentive awards. One half of the equity incentive awards will vest if Mr. Woodward remains in continuous employment with the Company on the vesting dates determined by the Board. The other half of the equity incentive awards will vest at various times during the term of the Agreement 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.

In addition, the Company will reimburse Mr. Woodward for his reasonable expenses related to travel between his current residence and Charlotte, North Carolina for a period of six months, and the Company will provide relocation assistance in accordance with the Company’s relocation policy for all employees. Mr. Woodward will also be eligible to participate in the standard employee benefit plans generally available to executive employees of the Company,

including long-term equity incentive plans, health insurance, life and disability insurance, employee stock purchase plan, 401(k) plan, and paid time off and paid holidays. The Company will also reimburse Mr. Woodward for his documented business expenses incurred in connection with his employment pursuant to the Company’s standard reimbursement expense policy and practices. The Company will further reimburse Mr. Woodward for up to $30,000 of his expenses incurred in connection with negotiating the Agreement.

If Mr. Woodward’s employment is terminated as a result of his death or disability, (i) Mr. Woodward’s time-based equity incentive awards (and his other unvested time-based equity awards, if any) will immediately vest and become payable, (ii) Mr. Woodward’s performance based equity incentive awards will pro-ratably vest for the year in which his employment terminates, contingent upon performance goal achievement for that year, and (iii) Mr. Woodward or his estate will be paid in a lump-sum a pro-rata portion of the annual bonus that he would have been paid had his employment not been terminated, 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 the Agreement), Mr. Woodward will be entitled to receive continued payment of his current base salary and medical and dental benefits for eighteen months. In addition, (i) a pro-rata portion of Mr. Woodward’s unvested, time-based equity incentive awards (and his other unvested time-based equity awards, if any) that would have vested at the end of the year of the termination will immediately vest and become payable, (ii) Mr. Woodward’s performance based equity incentive awards will pro-ratably vest for the year in which his employment terminates, contingent upon performance goal achievement for that year, and (iii) Mr. Woodward will be paid a lump-sum pro-rata portion of the annual bonus that he would have been paid had his employment not been terminated, 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 equity incentive awards (and other unvested time-based equity awards, if any) and his unvested performance based equity incentive awards will vest immediately and be paid at the time of the change of control. If Mr. Woodward’s employment is terminated within six months following a change control, either by the Company without cause or by Mr. Woodward for good reason, Mr. Woodward will be entitled to receive the same payments and benefits described above, except that the lump-sum pro-rata portion of the annual bonus will be based on the amount payable for attaining the target performance goals for that year, without regard to actual performance for the year.

The Agreement also provides that Mr. Woodward will not engage in competition with the Company during his employment or for eighteen months following termination of employment, and that he will comply with certain other post-termination restrictions.

The foregoing description of the Agreement is qualified in its entirety by reference to the full text of the Agreement, which is filed as Exhibit 10.1 to this Current Report on Form 8-K and is incorporated by reference herein.

There are no arrangements or understandings between Mr. Woodward and any other persons pursuant to which he was selected as a director, and he has no direct or indirect material interest in any transaction required to be disclosed pursuant to Item 404(a) of Regulation S-K.

Departure of Director and Officer

On June 7, 2012, Stephen H. Fraser stepped down as Interim President and Chief Executive Officer of the Company, effective as of June 7, 2012. Mr. Fraser also resigned from the Board effective as of June 7, 2012. Mr. Fraser will remain an employee through June 12, 2012 to support the leadership transition. All 1,224 shares of Mr. Fraser’s unvested, restricted stock became fully vested in connection with his resignation from the Board.

On June 7, 2012, the Company entered into a Consulting Agreement (the “Consulting Agreement”) with Mr. Fraser, whereby the Company will retain Mr. Fraser as a consultant effective June 12, 2012 for a period of one year. Mr. Fraser will provide the consulting services requested by the Company and will be paid $525 per hour for such consulting services. The foregoing description of the Consulting Agreement is qualified in its entirety by reference to the full text of the Agreement, which is filed as Exhibit 10.2 to this Current Report on Form 8-K and is incorporated by reference herein.

In addition, on June 7, 2012, the Company entered into Amendment No. 1 to the Employment Agreement (the “Amendment”) with Mr. Fraser. The Amendment provides that Mr. Fraser will resign as a member of the Board effective as of the commencement of the successor CEO with the Company, and that he and the Board could agree to extend his employment for a transition period following the hiring of a successor CEO. The foregoing description of the Amendment is qualified in its entirety by reference to the full text of the Amendment, which is filed as Exhibit 10.3 to this Current Report on Form 8-K and is incorporated by reference herein.

Item 5.07. Submission of matters to a Vote of Security Holders.

The Company held its Annual Meeting of Shareholders on June 7, 2012. At the meeting, shareholders elected each of the nominees nominated by the Board to serve a three year term on the Company’s Board. Shareholders also ratified the appointment of Ernst & Young LLP as the Company’s independent registered public accounting firm for fiscal 2012. Finally, shareholders approved, on an advisory basis, the Company’s executive compensation program for its named executive officers, as described in the Company’s Proxy Statement.

Set forth below are the final voting results for each of the proposals.

Election of Director Nominees

Proposal to Ratify Appointment of Ernst & Young LLP as Independent Registered Public Accounting Firm

Approval of Company’s Executive Compensation for Named Executive Officers

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.

EXHIBITS