Exhibit 99.1

4064 Colony Road, Suite 200
Charlotte, NC 28211
704.973.7000
www.horizonlines.com

N e w s   R e l e a s e

For information contact:

Jim Storey
Director of Investor Relations & Corporate Communications
704.973.7107
jstorey@horizonlines.com

HORIZON LINES ANNOUNCES RESTRUCTURING PLAN

Annualized labor-related savings estimated at $7 - $10 million

CHARLOTTE, NC, November 10, 2008 — Horizon Lines, Inc. (NYSE: HRZ) today announced a non-union workforce restructuring initiative targeted at reducing annualized labor-related costs by an estimated $7 million to $10 million.

The company intends to reduce its workforce by at least 10%, or approximately 70 of its 700-plus non-union employees. Initially, the company will offer a voluntary severance program to certain eligible non-union employees. If the company is unable to achieve anticipated reductions from the voluntary program, it intends to implement an involuntary severance program for non-union employees. The company expects to complete the workforce reduction initiative by January 31, 2009, and it is expected to result in a fourth-quarter 2008 charge of approximately $3.5 million to $5 million pretax, or $0.11 to $0.16 per fully diluted share. The final annualized savings and associated costs of the initiative will depend on the actual mix of associates who are ultimately included in either the voluntary or involuntary program.

“We continue to face a very difficult macro-economic environment that is having a significant adverse impact on the markets we serve,” said Chuck Raymond, Chairman, President and Chief Executive Officer. “We expect these challenges to continue through at least 2009 and are taking the appropriate, necessary steps to adjust our business without impacting our ability to continue providing excellent service to all our customers and execute our business strategy. We also are continuing to evaluate all other non-personnel aspects of our business and assess additional restructuring opportunities to remove costs from our system. At the same time, we will continue to utilize our Horizon EDGE process to improve efficiencies of our ongoing business.

“While our company remains well-capitalized, with strong liquidity, our focus for 2009 will be on conserving cash and removing costs from our organization wherever possible,” Mr. Raymond

said. “Our executive leadership remains intact and is committed to guiding Horizon Lines through this challenging economic environment.”

About Horizon Lines
Horizon Lines, Inc. is the nation’s leading domestic ocean shipping and integrated logistics company comprised of two primary operating subsidiaries. Horizon Lines, LLC owns or leases a fleet of 21 U.S.-flag containerships and 5 port terminals linking the continental United States with Alaska, Hawaii, Guam, Micronesia and Puerto Rico. Horizon Logistics, LLC offers customized logistics solutions to shippers from a suite of transportation and distribution management services designed by Aero Logistics, information technology developed by Horizon Services Group and intermodal trucking and warehousing services provided by Sea-Logix. Horizon Lines, Inc. is based in Charlotte, NC, and trades on the New York Stock Exchange under the ticker symbol HRZ.

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, “expect,” “estimate,” “intend,” “plan,” “target,” “will,” and similar expressions or phrases identify forward-looking statements.

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 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.

# # #