Exhibit 99.2

PRESS RELEASE For
information contact:

Investment Community		Trade Media		Financial News Media
Jim Storey		Barbara Yeninas		Meaghan Repko
Director, Investor Relations		BSY Associates		Joele Frank, Wilkinson Brimmer Katcher
704-973-7107		732-817-0400		212-355-4449

HORIZON LINES ANNOUNCES MANAGEMENT CHANGES

CHARLOTTE, NC (February 24, 2011) — Horizon Lines, Inc. (NYSE: HRZ) today announced that the company’s Board of Directors has named Alex J. Mandl to the position of Chairman and appointed Stephen H. Fraser as interim President and Chief Executive Officer (CEO), succeeding Chairman, President and Chief Executive Officer Charles G. “Chuck” Raymond, who is retiring.

Additionally, Brian W. Taylor has been named Executive Vice President and Chief Operating Officer (COO), succeeding John V. Keenan, who has been granted a leave of absence. Mr. Taylor assumes the COO responsibilities in addition to his current role as Chief Commercial Officer. At the same time, the Board has promoted Michael T. Avara from Senior Vice President and Chief Financial Officer to Executive Vice President and Chief Financial Officer. All changes are effective March 11, 2011.

In naming Mr. Mandl and Mr. Fraser to the positions of Chairman and Chief Executive Officer, respectively, the Board has split the responsibilities of chairman and chief executive officer into two positions. Both Mr. Mandl and Mr. Fraser are members of the company’s Board. Mr. Fraser will serve as President and Chief Executive Officer until the Board identifies a new CEO to serve on a permanent basis. The Board is initiating a search process and is engaging a leading executive search firm to assist in identifying candidates to serve as CEO.

“Chuck Raymond and John Keenan are highly regarded veterans of the industry and have made tremendous contributions to our company over their decades of service,” said William J. Flynn, Lead Independent Director of the Horizon Lines Board of Directors. “Both have been instrumental in the growth of the company and steered it through recent challenges presented by the global economic recession and the Department of Justice investigation.

“Horizon Lines is fortunate to have talented, committed and highly qualified directors and executives who are ready to step into these roles, and we are confident that we have the right team in place to lead the company forward,” Mr. Flynn continued. “Horizon Lines is moving ahead on its current strategies and business goals, and we expect a seamless transition for our customers and for all of our stakeholders.”

About Alex J. Mandl

Mr. Mandl has served as a Director of the company since June 2007. Mr. Mandl has been the Chairman of the Board of Gemalto, a global leader in digital security, since December 2007. From June 2006 to November 2007, he was the Executive Chairman of Gemalto. Mr. Mandl also serves as the President and CEO and a member of the Board of Gemplus, positions he

Horizon Lines News Release		Page 2 of 3

held since August 2002. He has served as a principal in ASM Investments, a company focusing on technology investments, since April 2001. Previously, Mr. Mandl served as Chairman and CEO of Teligent, and President and COO of AT&T. Prior to AT&T he served as Chairman and CEO of Sea-Land Service, Inc., the domestic and international predecessor of Horizon Lines. At Sea-Land Service, Mr. Mandl played an integral role in the successful turnaround efforts of the company, including growing revenue by nearly 100 percent during his tenure. Mr. Mandl currently serves on the boards of Gemalto and Dell Inc. Mr. Mandl holds an MBA from the University of California at Berkeley and a BA in economics from Willamette University.

About Stephen H. Fraser

Mr. Fraser has served as a Director of the company since June 2010. From September 2008 to December 2009, he served as Executive Vice President, Corporate Strategy, at GENCO Supply Chain Solutions, where he also served as CEO of GENCO’s three reverse logistics business units. From May 2000 to January 2008, Mr. Fraser was President and CEO of May Logistics Services and ADS Logistics, two logistics companies with common ownership. From 1996 to 2000, Mr. Fraser served in a variety of leadership positions at GATX Corporation. From 1988 to 1995, Mr. Fraser was focused on building a series of companies involved in intermodal environmental logistics, which he joint ventured with, and subsequently sold to, GATX Capital. Mr. Fraser began his career and worked 10 years at the international container, crane and vessel leasing company Sea Containers, where he served in both domestic and international positions. He serves on the boards of Nautilus Holding Corporation and Focus Products Group. Mr. Fraser holds a BA in Economics and Political Science from Columbia University.

About Brian W. Taylor

Mr. Taylor, previously Senior Vice President, Chief Commercial Officer, is responsible for the company’s sales and pricing teams and recently led the company’s expansion into the commercial Asia market, which launched in December 2010. A 27-year veteran of Horizon Lines and its predecessors, Mr. Taylor has held management positions in sales and operations in the U.S. and Asia. He received his Bachelor of Commerce and Master of Business Administration in Economics and Financial Management from Concordia University.

About Michael T. Avara

Mr. Avara has served as Senior Vice President and Chief Financial Officer of Horizon Lines since 2008. He is responsible for the accounting, finance, treasury, risk management and investor relations functions of the company. Prior to rejoining Horizon Lines in March 2004, Mr. Avara, a certified public accountant, spent 20 years in various accounting and finance functions at CSX Corporation and its subsidiaries, including Horizon Lines and Sea-Land Service, Inc. Mr. Avara received both a MBA in Finance and a BA in Accounting from Loyola College in Baltimore, Maryland.

About Horizon Lines

Horizon Lines, Inc., is the nation’s leading domestic ocean shipping and integrated logistics company. The company owns or leases a fleet of 20 U.S.-flag containerships and operates five port terminals linking the continental United States with Alaska, Hawaii, Guam, Micronesia, and Puerto Rico. The company provides express trans-Pacific service between the U.S. West Coast and the ports of Ningbo and Shanghai in China, manages a domestic and overseas service partner network and provides integrated, reliable and cost competitive logistics solutions. Horizon Lines, Inc., is based in Charlotte, NC, and trades on the New York Stock Exchange under the ticker symbol HRZ.

Horizon Lines News Release		Page 3 of 3

Forward Looking Statements

The information contained in this press release should be read in conjunction with our filings made with the Securities and Exchange Commission. This press release 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”, “seeking,” “scheduled,” “expects,” “anticipates” and similar expressions or phrases identify forward-looking statements.

See the section entitled “Risk Factors” in our Form 10-K filed with the SEC on February 4, 2010, and in our Form 10-Q for the period ended June 20, 2010, for a discussion of risks and uncertainties that may affect us. In light of these risks and uncertainties, expected results or other anticipated events or circumstances discussed in this press release might not occur. We undertake no obligation, and specifically decline any obligation, to publicly update or revise any forward-looking statement, whether as a result of new information, future events or otherwise. 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.

# # #