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): March 26, 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)

Not Applicable

(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 (see General Instruction A.2. below):

Horizon Lines, Inc. (the “Company”) announced that it and certain of its wholly owned subsidiaries have entered into Restructuring Support Agreements, dated March 26, 2012 (the “Restructuring Agreements”) with certain holders of more than 96% of its 11.00% first lien secured notes due 2016 (the “First Lien Secured Notes”), 13-15% second lien secured notes due 2016 (the “Second Lien Secured Notes”) and 6.00% Series A Convertible Senior Secured Notes due 2017 and 6.00% Series B Mandatorily Convertible Senior Secured Notes (the “Convertible Secured Notes”, together with the First Lien Secured Notes and the Second Lien Secured Notes, the “Notes”) to further deleverage the Company’s balance sheet in connection with and contingent upon a restructuring of the vessel charter obligations related to the Company’s discontinued trans-Pacific service.

The Restructuring Agreements provide, among other things, that substantially all of the remaining Convertible Senior Secured Notes will be converted into 90% of the Company’s stock, or warrants for non-U.S. citizens (subject to limited equity retention by existing equity holders on terms to be agreed, and to dilution for a management incentive plan). The remaining 10% of the Company’s common stock would be available in connection with the restructuring of Horizon’s vessel obligations. To that end, the conversion of the Convertible Secured Notes is contingent upon a number of conditions, including the Company’s restructuring of its charter obligations with respect to the vessels. The holders of the Notes that executed the Restructuring Agreements have agreed not to transfer their Notes before the occurrence of a termination event which would terminate the Restructuring Agreements unless the transferee agrees to the terms of the Restructuring Agreements. Termination events include, but are no limited to, (i) a breach by the Company of its obligations under the Restructuring Agreements; (ii) the occurrence of an event of default in the indenture governing the Notes or in the charters identified in the Restructuring Agreements; (iii) the occurrence of any material changes or waivers in certain of the Company’s financing documents which are not reasonably satisfactory to a majority of the holders of Notes that executed the Restructuring Agreements; and (iv) the failure to restructure the charter obligations by April 5, 2012. The Restructuring Agreements terminate automatically on April 30, 2012.

A copy of the form of Restructuring Agreements is filed as Exhibit 10.1 to this Current Report on Form 8-K, and the information in the form of Restructuring Agreements is incorporated into this Item 1.01 by this reference. A copy of the press release is attached as Exhibit 99.1 hereto, and the first eight paragraphs of the press release are herein incorporated by reference.

On March 27, 2012, the Company issued a press release announcing its preliminary earnings results for the fourth fiscal quarter ended December 25, 2011. A copy of the press release is filed as Exhibit 99.1 hereto, and the section entitled “Preliminary Fourth-Quarter Earnings Results” is incorporated herein by reference.

The information under Items 2.02 and 7.01 in this Current Report, and the section entitled “Preliminary Fourth-Quarter Earnings Results” in Exhibit 99.1 hereto, is being furnished and shall not be deemed “filed” for the purposes of Section 18 of the Securities Exchange Act of 1934, as amended, nor shall this information be deemed incorporated by reference into any registration statement or other document pursuant to the Securities Act of 1933, as amended, except as shall be expressly set forth by specific reference in such a filing.

The disclosure under Item 2.02 of this Current Report on Form 8-K is incorporated herein 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. 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,” “intend,” “expect,” “would,” “could,” “must,” “may,” and similar expressions or phrases identify forward-looking statements.

Factors that may cause expected results or anticipated events or circumstances discussed in this press release to not occur or to differ from expected results include: our ability to conclude agreements with our noteholders, and the counterparties to the vessel charters and their lenders, resulting in a restructuring of our debt and the vessel charters; our ability to maintain adequate liquidity to operate our business; our ability to make interest payments on our outstanding indebtedness; failure to comply with the terms of our probation imposed by the court in connection with our pleas relating to antitrust and environmental matters; volatility in fuel prices; decreases in shipping volumes; the reaction of our customers and business partners to our announcements and filings, including those referred to herein; government investigations related to (i) the imposition of fuel surcharges in connection with government contracts, (ii) regulations covering products transported on our vessels, including the FDA and USDA, or (iii) any other government investigations and legal proceedings; suspension or debarment by the federal government; compliance with safety and environmental protection and other governmental requirements; increased inspection procedures and tighter import and export controls; repeal or substantial amendment of the coastwise laws of the United States, also known as the Jones Act; catastrophic losses and other liabilities; our ability to integrate new and retain existing management; the successful start-up of any Jones-Act competitor; failure to comply with the various ownership, citizenship, crewing, and U.S. build requirements dictated by the Jones Act; the arrest of our vessels by maritime claimants; severe weather and natural disasters; and the aging of our vessels and unexpected substantial dry-docking or repair costs for our vessels.

All forward-looking statements involve risk and uncertainties. In light of these risks and uncertainties, expected results or other anticipated events or circumstances discussed in this Current Report on Form 8-K might not occur. The forward-looking statements included in this Current Report on Form 8-K are made only as of the date they are made and the company undertakes no obligation to update any such statements, except as otherwise required by applicable law. See the section entitled “Risk Factors” in our Form 10-Q filed with the SEC on November 4, 2011, for a more complete discussion of these risks and uncertainties and for other risks and uncertainties. Those factors and the other risk factors described therein are not necessarily all of the important factors that could cause actual results or developments to differ materially from those expressed in any of our forward-looking statements. Other unknown or unpredictable factors also could harm our results. Consequently, there

can be no assurance that actual results or developments anticipated by us will be realized or, even if substantially realized, that they will have the expected consequences.

NON-GAAP FINANCIAL MEASURES

Item 2.02 and 7.01, and Exhibit 99.1 hereto, contain adjusted operating income as a financial measure. This is a non-GAAP financial measure within the meaning of Regulation G promulgated by the Securities and Exchange Commission.

The Company believes that, in addition to GAAP-based financial information, the non-GAAP amounts are meaningful disclosures because each are components of measures used by the Company’s Board of Directors and management team to: evaluate our operating performance; make day-to day operating decisions; facilitate internal comparisons to competitors’ results and the marine container shipping industry in general; and to provide useful information for the understanding of ongoing operations, taking into account the impact of specific individual items. Non-GAAP measures are also components of certain targets used by the Company’s Board of Directors and management team to evaluate progress related to the payment of certain discretionary bonuses, as well as to determine compliance with a springing financial covenant under the Company’s asset-based revolving credit facility, which is tested only when availability under this facility falls below a minimum threshold. Because all companies do not use identical calculations, the presentation of non-GAAP financial measures may not be comparable to other similarly titled measures of other companies.

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