Exhibit 99.2

HORIZON LINES REPORTS SOLID SECOND QUARTER 2007 EARNINGS

CHARLOTTE, North Carolina, July 27, 2007 — Horizon Lines, Inc. (NYSE:HRZ) reported solid earnings for the second quarter of 2007.

Net income for the second quarter of 2007 was $9.6 million or $.28 per diluted share compared to net income of $6.4 million or $.19 per diluted share for the second quarter of 2006. After adjustment to exclude the non-recurring loss on extinguishment of debt in 2007 and secondary offering expenses in 2006, and to retroactively apply tonnage tax to 2006, adjusted net income was $10.0 million or $.29 per diluted share in 2007’s second quarter, versus $9.7 million or $.29 per diluted share in the second quarter of 2006.

Operating revenue grew by $5.9 million or 2.0% in the second quarter of 2007 to $295.7 million, compared to $289.8 million for the second quarter of 2006.

Operating income in the second quarter of 2007 was $22.9 million versus $22.4 million in 2006’s second quarter. Absent non-recurring secondary offering expenses, adjusted operating income in the second quarter of 2006 would have been $23.3 million.

Earnings before net interest expense, taxes, depreciation and amortization (EBITDA) was $39.5 million for the second quarter of 2007 compared to $39.8 million for the 2006 second quarter. Excluding the non-recurring loss on extinguishment of debt in 2007 and secondary offering expenses in 2006, adjusted EBITDA would have been $40.0 million in the second quarter of 2007 in contrast to $40.7 million for the second quarter of 2006.

“Despite some lingering volume softness, we once again overcame challenges and delivered solid earnings in the second quarter of 2007”, said Chuck Raymond, Chairman, President and Chief Executive Officer. “Benefits generated by our Horizon EDGE process re-engineering and customer service program, stringent cost controls and unit revenue and cargo mix improvements, all combined to more than offset the volume shortfall. We completed our Transpacific (TP1) fleet enhancement initiative and all five new vessels are now deployed and are operating in the new TP1 service. Investment in our business continued with the addition of 707 new refrigerated containers and 238 new flat racks. Finally, we initiated a process to refinance our capital structure that we expect will result in reduced interest expense going forward when completed in the third quarter of 2007.”

The Company also updated its earnings guidance for the full year 2007, with projections of operating revenue at $1,190 — $1,200 million, EBITDA at $168 — $173 million, diluted earnings per share (EPS) at $1.46 — $1.58 and free cash flow at $30 — $37 million. Earnings guidance for the third quarter of 2007 was also provided, with forecasts of operating revenue of $314 — $322 million, EBITDA of $49 — $52 million and diluted EPS of $0.56 — $0.63. The earnings guidance for the third quarter and full year does not reflect any impact from the Company’s recently announced planned refinancing.

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-240-6709 and asking for the Horizon Lines Second 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. Alternatively, 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 Jones Act container shipping and integrated logistics company with a fleet of 21 U.S.—flag vessels and service routes linking the continental United States with Alaska, Hawaii, Guam, Micronesia and Puerto Rico. A fully integrated service provider of ocean transportation, trucking, terminal and warehousing operations, Horizon Lines also owns Horizon Services Group, an organization with a diversified offering of transportation management systems and customized software solutions being marketed to shippers, carriers, and other supply chain participants. Horizon Lines, Inc. trades on the New York Stock Exchange under the ticker symbol HRZ.

Forward Looking Statement:

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 filed with the SEC on March 2, 2007 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.

Media Contact:

Michael Avara of Horizon Lines, Inc.

1-704-973-7000

mavara@horizonlines.com