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): December 7, 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)

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):

Item 1.01. Entry into a Material Definitive Agreement.

In connection with the amendment to the Restated Certificate of Incorporation of Horizon Lines, Inc. (the “Company”), described in Item 5.03 below, the following documents were entered into:

Warrant Agreement

On December 7, 2011, the Company entered into a warrant agreement with The Bank of New York Trust Company, N.A., as warrant agent. As of the date hereof, no warrants have been issued under this warrant agreement.

Each warrant, which would be issued to redeem an “excess share” of the Company’s common stock, will entitle the holder to purchase one share of the Company’s common stock at a price of $0.01 per share, subject to certain adjustments. The warrants may be exercised by cashless exercise or they may be converted into common stock without any required payment of the exercise price. The warrants may not be exercised for cash. All warrants will expire on the 25th anniversary of the warrant agreement. The warrants are issued as separate instruments from the Company’s common stock and are permitted to be transferred independently from the Company’s common stock. Warrant holders will not be permitted to exercise or convert their warrants for shares of common stock if and to the extent that the shares issuable upon exercise or conversion would constitute “excess shares” if they were issued. In addition, a warrant holder who cannot establish to the Company’s reasonable satisfaction that it is a United States citizen will not be permitted to exercise or convert its warrants to the extent the receipt of the common stock upon exercise or conversion would cause such person or any person whose ownership position would be aggregated with such person to exceed 4.9% of the Company’s outstanding common stock. The exercise price and number of shares of the Company’s common stock issuable on exercise or conversion of the warrants may be adjusted in certain circumstances, including in the event of a stock dividend, stock split, stock combination, merger or consolidation. Warrant holders will not have any rights or privileges of holders of the Company’s common stock, including any voting rights, until they exercise or convert their warrants and receive shares of the Company’s common stock. After the issuance of shares of the Company’s common stock upon exercise of the warrants, each holder will be entitled to one vote for each share held of record on all matters to be voted on by stockholders. The warrant agreement further provides that the warrants may be exchanged at the Company’s option for warrants governed by the existing Warrant Agreement, dated October 5, 2011, among the Company and The Bank of New York Trust Company, N.A., as warrant agent, that was entered into in connection with the Company’s previously disclosed exchange offer relating to its 4.25% Convertible Senior Notes due 2012.

The description of the warrant agreement is qualified in its entirety by reference to the full text of the warrant agreement which is attached hereto as Exhibit 4.1 and is incorporated herein by reference.

Redemption Notes Indenture

On December 7, 2011, the Company entered into an indenture with The Bank of New York Trust Company, N.A., as trustee, relating to redemption notes. As of the date hereof, no redemption notes have been issued.

The redemption notes may be issued in consideration for “excess shares” and will be interest-bearing promissory notes of the Company with a maturity of not more than 10 years from the date of issue and bear interest at a fixed rate equal to the yield on the U.S. Treasury Note having a maturity comparable to the term of such promissory notes as published in The Wall Street Journal or comparable publication at the time of the issuance of the redemption notes. The terms of the redemption notes will consist of covenants to pay principal and interest and any other obligations required to be made part of the indenture by reference to the Trust Indenture Act of 1939, as amended. The redemption notes will be redeemable at par plus accrued but unpaid interest.

The description of the indenture relating to the redemption notes is qualified in its entirety by reference to the full text of the indenture relating to the redemption notes which is attached hereto as Exhibit 4.2 and is incorporated herein by reference.

Amendment to Warrant Agreement and Warrants

On December 7, 2011, the Company and The Bank of New York Trust Company, N.A., as warrant agent (the “Warrant Agent”) entered into an amendment to (i) the Warrant Agreement (the “Warrant Agreement”) dated October 5, 2011, between the Company and the Warrant Agent and (ii) the outstanding warrants thereunder, to make certain amendments which relate to the 1–for–25 reverse stock split of the Company’s common stock described below pursuant to the terms of the Warrant Agreement. The amendment also amends the warrants issued under the Warrant Agreement.

The description of the amendment to the warrant agreement is qualified in its entirety by reference to the full text of the amendment which is attached hereto as Exhibit 4.3 and is incorporated herein by reference.

Item 5.03. Amendments to Articles of Incorporation or Bylaws; Change in Fiscal Year.

On December 7, 2011, in connection the vote of stockholder at the Company’s special meeting on December 2, 2011, the Company filed with the Secretary of State of Delaware a restated Certificate of Incorporation (the “Restated Certificate of Incorporation”) to (i) effect the 1–for–25 reverse stock split of the Company’s common stock, (ii) authorize the issuance of warrants in lieu of cash or redemption notes in consideration for “excess shares” to facilitate compliance with the Jones Act and (iii) combine into one document all of the provisions of the existing Amended and Restated Certificates of Incorporation, including the amendments noted above.

The description of the Restated Certificate of Incorporation is qualified in its entirety by reference to the full text of the restated Certificate of Incorporation which is attached hereto as Exhibit 3.1 and is incorporated herein by reference.

Item 8.01. Other Events.

On December 8, 2011, the Company issued a press release announcing the 1–for–25 reverse stock split of the Company’s common stock and other amendments related to the restated Certificate of Incorporation.

A copy of the press release is attached hereto as Exhibit 99.1 and is incorporated herein by reference.

Item 9.01. Financial Statements and Exhibits

(d) 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

6