Exhibit 99.2

HORIZON LINES REPORTS RECORD FIRST QUARTER EARNINGS

CHARLOTTE, North Carolina, April 26, 2007 – Horizon Lines, Inc. (NYSE:HRZ) today reported record earnings for the first quarter of 2007.

Net income for the first quarter of 2007 was $7.1 million or $.21 per basic and diluted share compared to $2.4 million or $.07 per basic and diluted share in the 2006 first quarter. After adjustments to exclude a deferred tax revaluation benefit in 2007, and apply tonnage tax on a pro-forma basis in 2006, adjusted net income was $4.5 million or $.13 per basic and diluted share in the first quarter of 2007 versus $3.6 million or $.11 per basic and diluted share for the first quarter of 2006. The first quarter 2007 adjusted earnings per share of $.13 was within the Company’s previously announced earnings guidance of $.10 - $.15 per share and equaled the analysts’ consensus.

Operating revenue was essentially flat, falling slightly by $1.2 million or .4% to $273.7 million for the first quarter of 2007 compared to $274.9 million during the 2006 first quarter. The revenue decline was primarily due to a 6.5% reduction in volumes, reflecting continued soft market conditions in Puerto Rico and an extended winter in Alaska. Higher margin cargo mix, general rate increases and fuel recoveries nearly offset the volume-related revenue decline.

Operating income for the first quarter of 2007 grew by 3.8% to $16.5 million versus $15.9 million in the first quarter of 2006. The increase in operating income was driven by the Company’s on-going focus on controlling operating costs and its Horizon EDGE program.

Earnings before net interest expense, taxes, depreciation and amortization (EBITDA) was $33.7 million for the first quarter of 2007, growing by 6.0% from $31.8 million in the 2006 first quarter.

“Horizon Lines delivered record first quarter earnings and our 21^st consecutive quarter of adjusted EBITDA growth, despite less than ideal market conditions,” said Chuck Raymond, Chairman, President and Chief Executive Officer. “Stringent cost controls, Horizon EDGE savings, cargo mix upgrades and rate improvements all combined to more than offset some

lingering volume softness. Horizon EDGE, our customer service and process improvement program, captured all of its first quarter milestones and is delivering increasing benefits. Our TP1 fleet enhancement initiative is on track and the deployment of this new tonnage is nearing completion. We continue to invest in our business and were honored once again as the recipient of two prestigious service excellence awards in the first quarter. Additionally, we continue to focus on reducing our leverage, prepaying $25 million of debt on March 30^th, at the beginning of the second quarter. The Horizon Lines team overcame challenging conditions in the first quarter, as they have so many times in the past, and we look forward to an improving market environment throughout the remainder of 2007.”

The Company updated its earnings guidance for the full year 2007, with projections of operating revenue at $1,200 - $1,210 million, EBITDA of $173 - $180 million and earnings per share increased to $1.62 - $1.73, excluding a deferred tax revaluation benefit, on a lower effective tax rate assumption. Earnings guidance for the second quarter 2007 was also provided, with forecasts of operating revenue of $295 - $300 million, EBITDA of $40 - $43 million and EPS of $.29 - $.34.

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-5318 and asking for the Horizon Lines First 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, operating 16 U.S.-flag vessels on routes linking the continental United States with Alaska, Hawaii, Guam, and Puerto Rico. Horizon Lines also owns Horizon Services Group, an organization with a diversified offering of cargo management and tracking services 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 final 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, or mavara@horizonlines.com.

Horizon Lines, Inc.

Unaudited Condensed Consolidated Balance Sheets

(in thousands, except per share data)

	March 25, 2007			December 24, 2006(1)
Assets
Current assets
Cash and cash equivalents	$	44,190		$	93,949
Accounts receivable, net of allowance of $6,020 and $4,972 at March 25, 2007 and December 24, 2006, respectively		138,447			120,732
Deferred tax asset		9,615			11,586
Prepaid vessel rent		10,661			1,163
Materials and supplies		25,250			24,658
Other current assets		7,627			7,103
Total current assets		235,790			259,191
Property and equipment, net		183,047			188,652
Goodwill		306,724			306,724
Intangible assets, net		162,238			167,882
Other long-term assets		28,314			22,580
Total assets	$	916,113		$	945,029
Liabilities and Stockholders’ Equity
Current liabilities
Accounts payable	$	21,056		$	28,322
Current portion of long-term debt		2,244			6,758
Other accrued liabilities		108,535			126,548
Total current liabilities		131,835			161,628
Long-term debt, net of current		505,532			503,708
Deferred tax liability		30,829			31,339
Deferred rent		34,885			36,003
Other long-term liabilities		4,190			4,074
Total liabilities		707,271			736,752
Stockholders’ equity
Common stock, $.01 par value. 50,000 shares authorized and 33,617 and 33,591 shares issued and outstanding as of March 25, 2007 and December 24, 2006, respectively		337			336
Additional paid in capital		180,315			179,599
Accumulated other comprehensive loss		(986	)		(1,011	)
Retained earnings		29,176			29,353
Total stockholders’ equity		208,842			208,277
Total liabilities and stockholders’ equity	$	916,113		$	945,029

(1) The balance sheet at December 24, 2006 has been derived from the audited financial statements of Horizon Lines, Inc.

Horizon Lines, Inc.

Unaudited Condensed Consolidated Statements of Operations

(in thousands, except per share amounts)

	Quarters Ended
	March 25, 2007			March 26, 2006
Operating revenue	$	273,664		$	274,934
Operating expense:
Operating expense (excluding depreciation expense)		217,681			219,924
Depreciation and amortization		13,467			12,503
Amortization of vessel dry-docking		3,760			3,414
Selling, general and administrative		21,893			22,922
Miscellaneous expense, net		384			299
Total operating expense		257,185			259,062
Operating income		16,479			15,872
Other expense (income):
Interest expense, net		11,214			11,720
Other (income) expense, net		(3	)		15
Income before income tax (benefit) expense		5,268			4,137
Income tax (benefit) expense		(1,784	)		1,771
Net income	$	7,052		$	2,366
Net income per share:
Basic	$	0.21		$	0.07
Diluted	$	0.21		$	0.07
Number of shares used in calculations:
Basic		33,613			33,544
Diluted		34,135			33,596
Dividends declared per common share	$	0.11		$	0.11

Horizon Lines, Inc.

Unaudited Condensed Consolidated Statements of Cash Flows

(in thousands)

	Quarters Ended
	March 25, 2007			March 26, 2006
Cash flows from operating activities:
Net income	$	7,052		$	2,366
Adjustments to reconcile net income to net cash used in operating activities:
Depreciation		8,577			7,613
Amortization of other intangible assets		4,890			4,890
Amortization of vessel dry-docking		3,760			3,414
Amortization of deferred financing costs		788			805
Deferred income taxes		(2,069	)		1,675
Gain on equipment disposals		(148	)		(275	)
Stock-based compensation		335			99
Accretion of interest on 11% senior discount notes		2,386			2,208
Changes in operating assets and liabilities
Accounts receivable		(17,715	)		(14,893	)
Materials and supplies		(643	)		1,143
Other current assets		(10,022	)		(2,000	)
Accounts payable		(7,266	)		3,271
Accrued liabilities		(24,044	)		(6,912	)
Vessel dry-docking payments		(2,403	)		(4,235	)
Other assets/liabilities		(1,644	)		(842	)
Net cash used in operating activities		(38,166	)		(1,673	)
Cash flows from investing activities:
Purchases of property and equipment		(3,338	)		(2,718	)
Proceeds from the sale of property and equipment		565			940
Net cash used in investing activities		(2,773	)		(1,778	)
Cash flows from financing activities:
Principal payments on long-term debt		(5,074	)		(625	)
Dividends to stockholders		(3,691	)		(3,690	)
Costs associated with initial public offering		—			(158	)
Proceeds from exercise of stock options		35			—
Payments of financing costs		(43	)		(816	)
Payments on capital lease obligation		(47	)		(45	)
Net cash used in financing activities		(8,820	)		(5,334	)
Net decrease in cash and cash equivalents		(49,759	)		(8,785	)
Cash and cash equivalents at beginning of period		93,949			41,450
Cash and cash equivalents at end of period	$	44,190		$	32,665

Horizon Lines, Inc.

Adjusted Net Income

(in Millions)

	Quarters Ended
	March 25, 2007			March 26, 2006
Net Income	$	7.1		$	2.4
Adjustments(a)
Tonnage Tax Adjustments:
•     2007 Deferred Tax Revaluation Benefit		(2.6	)		—
•     2006 Proforma Impact		—			1.2
Adjusted Net Income	$	4.5		$	3.6

(a) These items are not anticipated to recur regularly in the ordinary course of business.

Horizon Lines, Inc.

Net Income / EBITDA Reconciliation

(in Millions)

	Quarters Ended
	March 25, 2007			March 26, 2006
Net Income	$	7.1		$	2.4
Interest Expense, Net		11.2			11.7
Tax (Benefit) Expense		(1.8	)		1.7
Depreciation & Amortization		17.2			16.0
EBITDA	$	33.7		$	31.8

Note: EBITDA is defined as net income plus net interest expense, income taxes, depreciation and amortization. We believe that EBITDA is a meaningful measure for investors as (i) EBITDA is a component of the measure used by our board of directors and management team to evaluate our operating performance, (ii) the senior credit facility contains covenants that require Horizon Lines Holding to maintain certain interest expense coverage and leverage ratios, which contain EBITDA and (iii) EBITDA is a measure used by our management team to make day-to-day operating decisions.