Exhibit 99.2

Horizon Lines Reports Fourth Quarter 2007 Earnings In Line With Expectations

CHARLOTTE, North Carolina, February 1, 2008 — Horizon Lines, Inc. (NYSE: HRZ), today reported results for the fourth quarter and full year ended December 23, 2007. Net income for the fourth quarter of 2007 was $10.7 million or $.32 per diluted share versus net income of $10.6 million or $.31 per diluted share in the fourth quarter of 2006.

“The fourth quarter of 2007 brought to a close a year of many accomplishments for Horizon Lines,” said Chuck Raymond, Chairman, President and Chief Executive Officer. “Over the past year, we have managed to offset soft market conditions in Puerto Rico and rising fuel costs by aggressively managing costs and introducing valuable complementary services to our customers. Going forward, we will continue to execute on our long term strategy of offering our customers innovative shipping and logistics solutions to enhance our core service offerings. We believe we are well positioned for continued growth and profitability in our markets.”

Fourth Quarter and Full Year 2007 Financial Highlights

“2007 presented some challenges and opportunities for us,” said Mark Urbania, Executive Vice President and Chief Financial Officer. “Despite the continuing soft market in Puerto Rico and unprecedented increases in fuel prices, we were able to generate net income and earnings per share that were in line with the 2006 fourth quarter and full year periods and our expectations. These challenges were offset by improved cargo mix, a stable rate environment in all three of our offshore markets, and the benefits of our cost reduction efforts. In addition, our debt refinancing and $28.5 million share repurchase in August of 2007 and our $50 million share buyback program initiated in November, which is now complete, will significantly benefit our shareholders in 2008 and beyond.”

Operating Revenue — Operating revenue increased by $28.5 million or 9.9% to $316.0 million for the quarter, compared to $287.5 million for the fourth quarter of 2006. The growth in revenue was driven by cargo mix upgrades, rate improvement and revenue from acquisitions, which more than offset some volume softness.

Operating Income — Operating income for the fourth quarter of 2007 was $20.5 million compared to $22.5 million for the fourth quarter of 2006. Absent the impact of secondary offering expenses, operating income in the 2006 fourth quarter would have been $22.9 million.

EBITDA and Adjusted EBITDA — Earnings before net interest expense, taxes, depreciation and amortization (EBITDA) was $35.9 million for the fourth quarter of 2007 compared to $37.9 million for the 2006 fourth quarter. Excluding the non-recurring loss on extinguishment of debt and secondary offering expenses, adjusted EBITDA would have been $38.9 million for the fourth quarter of 2006.

Net Income and Adjusted Net Income- Net income for the fourth quarter of 2007 was $10.7 million or $.32 per diluted share versus net income of $10.6 million or $.31 per diluted share in the fourth quarter of 2006. After adjustment to exclude the loss on early extinguishment of debt and secondary offering expenses, adjusted fourth quarter 2006 net income was $11.5 million or $.34 per diluted share.

2007 Full Year Results — For the full year 2007, net income was $28.9 million or $.85 per diluted share compared to net income of $72.4 million or $2.14 per diluted share in 2006. After adjustment to exclude non-recurring loss on extinguishment of debt in 2007 and 2006, secondary offering expenses in 2006, and certain tax adjustments in 2007 and 2006, adjusted net income was $45.9 million or $1.36 per diluted share in 2007 versus adjusted net income of $45.0 million or $1.33 per diluted share in 2006. Please see attached schedules for reconciliation of fourth quarter and full year 2007 and 2006 adjusted results and EBITDA amounts to reported results.

Share Repurchase — The Company completed its $50 million share repurchase program this past month.

Fourth Quarter and Full Year 2007 Performance Highlights

“Our team really pulled together to accomplish a number of significant achievements in 2007,” Raymond stated. “We successfully executed our TransPacific (TP-1) fleet enhancement initiative, and all five new vessels are now operating in the new TP-1 service. We also accomplished the re-deployment of our Jones Act tonnage. As a result, we now have the appropriate capacity in all trades to support volume growth in future years, which will further improve the cost efficiency and reliability of the ocean services we provide to our customers.”

“We completed a capital structure refinancing that is generating significant benefits in terms of a lower cost of capital, improved cash flow, enhanced flexibility and greater liquidity that will allow us to take advantage of future growth opportunities,” Raymond continued. “2007 also saw us accomplish a corporate realignment that resulted in the creation of Horizon Logistics, which will enable us to grow our fully integrated logistics services offerings. We also successfully completed the first full year of our Horizon EDGE process re-engineering and customer service program. Horizon EDGE is delivering significant process improvements that are benefiting our customers and associates, while yielding cost savings that have met our internal targets and have somewhat mitigated the softness in Puerto Rico. In addition, we successfully integrated the Hawaii Stevedores, Inc. and Aero Logistics acquisitions, which have been earnings and cash flow accretive since inception.”

Outlook

“Looking ahead, we expect solid earnings growth in our core shipping business and expect to see increased momentum in our new logistics business as we continue to implement our growth strategy in 2008,” Raymond said. “We believe we are well

positioned to significantly grow earnings and free cash flow in 2008, despite the uncertain national economic outlook.”

Based on current market conditions, the Company updated its earnings guidance for the full year 2008, with projections of operating revenue at $1,345 — $1,365 million, EBITDA at $175 — $185 million, and diluted earnings per share at $2.01 — $2.26. Free cash flow is projected at $115 - $125 million.

Webcast & Conference Call Information

Company executives will provide additional perspective on the Company’s earnings during a conference call beginning at 11:00 a.m. Eastern Time today. Those interested in participating in the call may do so by dialing 1-800-218-4007 and asking for the Horizon Lines Fourth Quarter 2007 Earnings Call. A hardcopy of the presentation materials may be printed from the Horizon Lines website, www.horizonlines.com, shortly before the start of the call. In addition, a live audio webcast of the call may be accessed at www.horizonlines.com. In order to access the live audio webcast please allow at least 15 minutes before the start of the call to visit Horizon Lines’ website and download and install any necessary audio/video software for the webcast.

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 operates 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 Holdings, 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, “believe,” “expect,” “anticipate,” “estimate,” “intend,” “plan,” “target,” “projects,” “likely,” “will,” “would,” “could,” 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. See the section entitled “Risk Factors” in our Form 10-K and Form 10-Q filed with the SEC on March 2, 2007 and October 26, 2007, respectively, for a more complete discussion of these risks and uncertainties and for other risks and uncertainties. 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.