UNITED STATES

SECURITIES AND EXCHANGE COMMISSION

WASHINGTON, D.C. 20549

Form 10-Q/A

Amendment No. 1

(Mark one)

For the quarterly period ended March 27, 2011

OR

For the transition period from              to             

Commission File Number 001-32627

HORIZON LINES, INC.

(Exact name of registrant as specified in its charter)

(704) 973-7000

(Registrant’s telephone number, including area code)

NOT APPLICABLE

(Former name, former address and former fiscal year, if changed since last report)

Indicate by check mark whether the registrant (1) has filed all reports required to be filed by Section 13 or 15(d) of the Securities Exchange Act of 1934 during the preceding 12 months (or for such a shorter period that the registrant was required to file such reports), and (2) has been subject to such filing requirements for the past 90 days.    Yes  x    No  ¨

Indicate by check mark whether the registrant has submitted electronically and posted on its corporate website, if any, every Interactive Data File required to be submitted and posted pursuant to Rule 405 of Regulation S-T (§ 232.405 of this chapter) during the preceding 12 months (or for shorter period that the registrant was required to submit and post such files).    Yes  ¨    No  ¨

Indicate by check mark whether the Registrant is a large accelerated filer, an accelerated filer, a non-accelerated filer or a smaller reporting company. See definition of “large accelerated filer,” “accelerated filer” and “smaller reporting company” in Rule 12b-2 of the Exchange Act. (Check one):

Indicate by check mark whether the registrant is a shell company (as defined in Rule 12b-2 of the Exchange Act).    Yes  ¨    No  x

Indicate the number of shares outstanding of each of the issuer’s classes of common stock, as of the latest practicable date.

As of July 25, 2011, 30,906,540 shares of common stock, par value $.01 per share, were outstanding.

EXPLANATORY NOTE

This Amendment No. 1 to the Quarterly Report on Form 10-Q for the fiscal quarter ended March 27, 2011 of Horizon Lines, Inc. (the “Company”), filed with the U.S. Securities and Exchange Commission on April 29, 2011 (the “Form 10-Q”), is being filed to (1) state that the Company’s Principal Executive Officer and Principal Financial Officer evaluated the Company’s disclosure controls and procedures, and (2) include the certifications required by Section 302 of the Sarbanes-Oxlely Act of 2002, amended to conform with the requirements of Rule 13a-15(f) and Rule 15d-15(f) of the Exchange Act.

Except as set forth above, no other changes have been made to the Form 10-Q, and this Amendment No. 1 does not amend, update or change any other items or disclosure found in the Form 10-Q. Further, this Amendment No. 1 does not reflect events that may have occurred after the filing of the Form 10-Q.

Item 4. Controls and Procedures

Disclosure Controls and Procedures

The Company’s management, including the Company’s Chief Executive Officer and Chief Financial Officer, evaluated the effectiveness of the Company’s disclosure controls and procedures as of the end of the fiscal quarter ending March 27, 2011. Based on such evaluation, each of the Company’s Chief Executive Officer and Chief Financial Officer has concluded that the Company’s disclosure controls and procedures are effective.

Changes in Internal Control

There were no changes in the Company’s internal control over financial reporting during the Company’s fiscal quarter ending March 27, 2011 that have materially affected, or are reasonably likely to materially affect, the Company’s internal control over financial reporting.

6. Exhibits

1

SIGNATURE

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 thereunto duly authorized.

Date: July 28, 2011

2