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): October 24, 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:

On October 24, 2011, Horizon Lines, Inc. (the “Company”) issued a press release announcing that it will discontinue its Five Star Express (FSX) trans-Pacific container shipping service between the U.S. West Coast, Guam and China. A decrease in eastbound freight rates from China to the United States over the past 12 months and increasing fuel prices factored heavily into the decision to discontinue the FSX services and direct all of the Company’s resources towards domestic ocean markets in Alaska, Hawaii and Puerto Rico. The final voyages in the FSX service are scheduled to depart from Shanghai, China on November 2, 2011 and to Guam and the surrounding islands from the U.S. West Coast on November 10, 2011.

The Company expects to cease all operations related to the FSX service during the fourth quarter and does not expect to have significant continuing involvement in the operations after the termination. Therefore, the Company will classify the FSX service as discontinued operations and expects to record a pretax restructuring charge of between $105 million and $110 million in fiscal fourth quarter 2011. The charge includes estimated costs to return excess rolling stock equipment, facility closures, severance, and vessel charter expense, net of estimated sub-charter income.

A copy of the press release is attached to this Current Report on Form 8-K as exhibit 99.1 and is incorporated in this Item 2.05 by reference.

SAFE HARBOR STATEMENT

The information contained in this Current Report on Form 8-K (including the exhibits hereto) should be read in conjunction with our filings made with the Securities and Exchange Commission. This Current Report on Form 8-K (including the exhibits hereto) contains “forward-looking statements” within the meaning of the federal securities laws. These forward-looking statements are intended to qualify for the safe harbor from liability established by the Private Securities Litigation Reform Act of 1995. Forward-looking statements are those that do not relate solely to historical fact. They include, but are not limited to, any statement that may predict, forecast, indicate or imply future results, performance, achievements or events. Words such as, but not limited to, “will,” “expect,” “scheduled” and similar expressions or phrases identify forward-looking statements.

All forward-looking statements involve risk and uncertainties. The occurrence of the events described, and the achievement of the expected results, depend on many events, some or all of which are not predictable or within our control. Actual results may differ materially from expected results.

Factors that may cause actual results to differ from expected results include:

In light of these risks and uncertainties, expected results or other anticipated events or circumstances discussed in this Form 8-K might not occur. The forward-looking statements included in this Form 8-K and the attached press release are made only as of the date they are made and we undertake no obligation to update any such statements, except as otherwise required by applicable law.

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