UNITED STATES

SECURITIES AND EXCHANGE COMMISSION

Washington, D.C. 20549

FORM 8-K/A

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 8, 2011

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:

Explanatory Note

This Current Report on Form 8-K/A is being filed as an amendment (“Amendment No. 1”) to the Current Report on Form 8-K filed by Horizon Lines, Inc. (the “Company”) on June 8, 2011 (the “Original 8-K”) to update Item 5.07, Submission of Matters to a Vote of Security Holders, in the Original 8-K regarding the results of the Company’s 2011 Annual Meeting of Shareholders held on June 2, 2011 (the “2011 Annual Meeting”). The sole purpose of this Amendment No. 1 is to disclose the Company’s decision regarding how frequently it will conduct a non-binding advisory vote on the compensation of the Company’s named executive officers. No other changes have been made to the Original 8-K.

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

At the 2011 Annual Meeting, the Company’s shareholders voted (on a non-binding advisory basis) that the Company annually conduct a non-binding advisory vote on executive compensation, as such compensation is disclosed in the proxy statement. On July 28, 2011, the Company’s Board of Directors, in light of this shareholder vote and other factors considered by the Board of Directors in making its original recommendation concerning the frequency of the vote on executive compensation, determined that the Company will annually hold the advisory vote on compensation for the Company’s named executive officers. This advisory vote will continue to be held annually until the Company’s shareholders next vote on how frequently future votes on executive compensation should be held

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.