Exhibit 99.2

HORIZON LINES REPORTS STRONG GAIN IN FIRST QUARTER EARNINGS

CHARLOTTE, North Carolina, April 28, 2006 – Horizon Lines, Inc. (NYSE:HRZ) reported a strong gain in the first quarter 2006 earnings compared to the first quarter of 2005.

Net income for the first quarter of 2006 was $2.4 million or $.07 per share versus a net loss of $(9.7) million or $(.52) per share in the first quarter of 2005. After adjustment for non-recurring expenses, net income in the first quarter of 2005 was $.3 million or $.01 per share.

Operating revenue increased by $17.3 million or 6.7% to $274.9 million for the first quarter of 2006, compared to $257.6 million during the 2005 first quarter.

Operating income for the first quarter of 2006 was $15.9 million versus $3.8 million in the first quarter of 2005. Absent non-recurring expenses, operating income for the first quarter of 2005 would have been $11.0 million.

Earnings before net interest expense, taxes, depreciation and amortization (EBITDA) was $31.8 million in the 2006 first quarter in comparison to $20.5 million in the first quarter of 2005. Excluding the non-recurring expenses, EBITDA was $27.7 million for the 2005 first quarter. Please see attached reconciliation from net income to EBITDA.

“Horizon Lines picked up in 2006 where we left off in 2005 and the year is off to a great start,” said Chuck Raymond, President and Chief Executive Officer. “All earnings measurements in the first quarter of 2006 were significantly better than in the first quarter of 2005. We closed the transaction on April 11^th to lease five new vessels for deployment in our TransPacific 1 Service in the first half of 2007. Investment in our container fleet continued with the acquisition of 1,000 40’ high cube dry containers in the first quarter. Validation of the success of our customer service efforts continued in 2006, with three awards for customer service received already this year.”

The Company confirmed its earnings guidance for the full year 2006, with projections of operating revenue at $1,140 - $1,160 million, EBITDA at $158 - $162 million and earnings per share (EPS) at $.85 - $.90. Earnings guidance for the second quarter of 2006 was also provided, with forecasts of operating revenue of $282 - $287 million, EBITDA of $38 - $40 million and EPS of $.18 - $.20.

Company executives will provide additional perspective on the Company’s quarterly results during its first quarter earnings 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-4186 and asking for the Horizon Lines Earnings Call. Presentation materials and a live audio webcast will be accessible at Horizon Lines’ website www.horizonlines.com. In addition, Horizon Lines’ detailed financial information contained in its Form 10-Q document will be posted on www.horizonlines.com after filing with the Securities and Exchange Commission after the earnings call.

Horizon Lines, Inc. is the nation’s leading Jones Act container shipping and integrated logistics company. It accounts for approximately 36% of total U.S. marine container shipments from the

continental U.S. to the three non-contiguous Jones Act markets, Alaska, Hawaii and Puerto Rico, and to Guam.

This press release includes “forward-looking statements,” as defined by federal securities laws, with respect to financial condition, results of operations and business. All forward-looking statements involve risk and uncertainties. The occurrence of the events described, and the achievement of the expected results, depend on many events, some of which are not predictable or within our control. Actual results may differ materially from expected results.

Factors that may cause actual results to differ from expected results include: substantial debt; restrictive covenants under our debt agreements; decreases in shipping volumes; our failure to renew our commercial agreements with Maersk; rising fuel prices; labor interruptions or strikes; job related claims; liability under multi-employer pension plans; compliance with safety and environmental protection and other governmental requirements; new statutory and regulatory directives in the Untied States addressing homeland security concerns; the successful start-up of any Jones Act competitor; increased inspection procedures and tight import and export controls; restrictions on foreign ownership of our vessels; repeal or substantial amendment of the Jones Act; escalation of insurance costs; catastrophic losses and other liabilities; the arrest of our vessels by maritime claimants; severe weather and natural disasters; our inability to exercise our purchase options for our chartered vessels; the loss of our key management personnel; actions by our significant stockholder, and legal or other proceedings to which we are or may become subject.

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.

Media Contact:

Michael Avara of Horizon Lines, Inc. 1-704-973-7000, or mavara@horizonlines.com

Horizon Lines, Inc. and Subsidiaries

Unaudited Condensed Consolidated Balance Sheets

($ in thousands)

	March 26, 2006			December 25, 2005(1)
Assets
Current assets
Cash and cash equivalents	$	32,665		$	41,450
Accounts receivable, net of allowance of $6,413 and $6,064 at March 26, 2006 and December 25, 2005, respectively		134,732			119,838
Income taxes receivable		726			470
Deferred tax asset		18,211			16,380
Materials and supplies		25,212			26,355
Other current assets		7,713			5,969
Total current assets		219,259			210,462
Property and equipment, net		194,939			200,597
Goodwill		306,724			306,724
Intangible assets, net		185,939			191,502
Other long term assets		22,418			18,034
Total assets	$	929,279		$	927,319
Liabilities and Stockholders’ Equity
Current liabilities
Accounts payable	$	25,639		$	22,368
Current portion of long term debt		2,500			2,500
Other accrued liabilities		114,454			118,483
Total current liabilities		142,593			143,351
Long term debt, net of current		529,151			527,568
Deferred tax liability		65,386			61,880
Deferred rent		39,358			40,476
Other long term liabilities		2,453			2,284
Total liabilities		778,941			775,559
Stockholders’ equity
Common stock, $.01 par value, 50,000,000 shares authorized and 33,544,170 shares issued and outstanding at March 26, 2006 and December 25, 2005		336			336
Additional paid in capital		179,531			179,590
Accumulated other comprehensive income		35			74
Retained deficit		(29,564	)		(28,240	)
Total stockholders’ equity		150,338			151,760
Total liabilities and stockholders’ equity	$	929,279		$	927,319

⁽¹⁾ The balance sheet at December 25, 2005 has been derived from the audited financial statements of Horizon Lines, Inc.

Horizon Lines, Inc. and Subsidiaries

Unaudited Condensed Consolidated Statements of Operations

($ in thousands)

	For the Period December 26, 2005 through March 26, 2006		For the Period December 27, 2004 through March 27, 2005
Operating revenue	$	274,934	$	257,562
Operating expenses:
Operating expense (excluding depreciation expense)		219,924		206,203
Selling, general and administrative		22,922		29,513
Depreciation and amortization		12,503		12,893
Amortization of vessel drydocking		3,414		3,798
Miscellaneous expense, net		299		1,314
Total operating expense		259,062		253,721
Operating income		15,872		3,841
Other expense:
Interest expense, net		11,720		12,852
Other expense, net		15		3
Income (loss) before income taxes		4,137		(9,014	)
Income tax expense (benefit)		1,771		(841	)
Net income (loss)	$	2,366	$	(8,173	)
Less: accretion of preferred stock		—		1,561
Net income (loss) available to common stockholders	$	2,366	$	(9,734	)
Net income (loss) per share:
Basic	$	0.07	$	(0.52	)
Diluted	$	0.07	$	(0.52	)
Number of shares used in calculations:
Basic		33,544,170		18,790,879
Diluted		33,596,230		18,790,879
Dividends declared per common share	$	0.11	$	—

Horizon Lines, Inc. and Subsidiaries

Unaudited Condensed Consolidated Statements of Cash Flows

($ in thousands)

	For the Period December 26, 2005 through March 26, 2006			For the Period December 27, 2004 through March 27, 2005
Cash flows from operating activities:
Net income (loss)	$	2,366		$	(8,173	)
Adjustments to reconcile net income (loss) to net cash used in operating activities:
Depreciation		7,613			8,003
Amortization of other intangible assets		4,890			4,890
Amortization of vessel drydocking		3,414			3,798
Amortization of deferred financing costs		805			780
Deferred income taxes		1,675			(841	)
Gain on equipment disposals		(275	)		(45	)
Stock-based compensation		99			6,412
Accretion of interest on 11% senior discount notes		2,208			3,082
Changes in operating assets and liabilities
Accounts receivable		(14,893	)		(16,902	)
Materials and supplies		1,143			(144	)
Other current assets		(2,000	)		1,667
Accounts payable		3,271			(4,955	)
Accrued liabilities		(6,912	)		(4,448	)
Vessel drydocking payments		(4,235	)		(5,101	)
Other assets/liabilities		(842	)		87
Net cash used in operating activities		(1,673	)		(11,890	)
Cash flows from investing activities:
Purchases of property and equipment		(2,718	)		(1,188	)
Proceeds from the sale of property and equipment		940			249
Net cash used in investing activities		(1,778	)		(939	)
Cash flows from financing activities:
Principal payments on long term debt		(625	)		(625	)
Dividend to stockholders		(3,690	)		—
Payment of financing costs		(816	)		—
Costs associated with initial public offering		(158	)		—
Sale of stock		—			1,108
Distribution to holders of preferred stock		—			(535	)
Payments on capital lease obligation		(45	)		(53	)
Net cash used in financing activities		(5,334	)		(105	)
Net decrease in cash and cash equivalents		(8,785	)		(12,934	)
Cash and cash equivalents at beginning of period		41,450			56,766
Cash and cash equivalents at end of period	$	32,665		$	43,832

Horizon Lines, Inc. and Subsidiaries

Adjusted Net Income

($ in millions)

	Quarter Ended
	March 26, 2006		March 27, 2005
Net Income (Loss)	$	2.4	$	(8.2	)
Adjustments:(a)
Stock Compensation Expense		—		6.4
Management Fees		—		0.8
Interest Expense Reduction		—		2.5
Tax Impact		—		(1.2	)
Total Adjustments		—		8.5
Adjusted Net Income	$	2.4	$	0.3

^(a) These charges are not expected to occur regularly in the ordinary course of business.

Horizon Lines, Inc. and Subsidiaries

Adjusted Operating Income

($ in millions)

	Quarter Ended
	March 26, 2006		March 27, 2005
Operating Income	$	15.9	$	3.8
Adjustments:(a)
Stock Compensation Expense		—		6.4
Management Fees		—		0.8
Total Adjustments		—		7.2
Adjusted Operating Income	$	15.9	$	11.0

^(a) These charges are not expected to occur regularly in the ordinary course of business.

Horizon Lines, Inc. and Subsidiaries

Net Income / EBITDA Reconciliation

($ in millions)

	Quarter Ended
	March 26, 2006		March 27, 2005
Net Income (Loss)	$	2.4	$	(8.2	)
Interest Expense, Net		11.7		12.8
Tax Expense (Benefit)		1.7		(0.8	)
Depreciation & Amortization		16.0		16.7
EBITDA		31.8		20.5
Stock Compensation Expense		—		6.4
Management Fee		—		0.8
Adjusted EBITDA	$	31.8	$	27.7

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