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

Horizon Lines, Inc. (the “Company”) is asking stockholders, among other items, to approve an amendment to the Company’s existing certificate of incorporation to authorize the issuance of warrants in lieu of cash or redemption notes as consideration for the Company’s redemption of shares of its common stock that constitute “excess shares” (as defined in the Company’s certificate of incorporation in effect at that time) to facilitate compliance with the Jones Act (the “Charter Amendment”). Additional details are set forth in the Company’s proxy statement filed with the Securities and Exchange Commission in connection with the special meeting of stockholders’ to be held on December 2, 2011.

Warrant Agreement

If stockholders approve the Charter Amendment and the Board of Directors of the Company implements the Charter Amendment, the Company intends to enter into a warrant agreement with The Bank of New York Trust Company, N.A., as warrant agent, as soon as reasonably practicable. 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. A form of the warrant agreement is attached hereto as Exhibit 10.1, and incorporated by reference herein.

Redemption Notes Indenture

If stockholders approve the Charter Amendment and the Board of Directors of the Company implements the Charter Amendment, the Company intends to enter into the indenture with The Bank of New York Trust Company, N.A., as trustee, as soon as reasonably practicable. The redemption notes may be issued in consideration for “excess shares” and will 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. A form of the indenture relating to the redemption notes is attached hereto as Exhibit 10.2, and incorporated by reference herein.

(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

4