Exhibit 99.1

PRESS RELEASE

For information contact:

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

HORIZON LINES REPORTS 2009 FINANCIAL RESULTS

• Adjusted Full-Year EBITDA Totals $112.7 Million

• Adjusted Full-Year Free Cash Flow Totals $70.5 million

• Fourth-Quarter Volume Down 4.2%; Rate, Net of Fuel, Flat from Year Ago

• Dividend Set at $0.05 per Share for First Quarter of 2010

CHARLOTTE, NC, January 29, 2010 — Horizon Lines, Inc. (NYSE: HRZ), today reported results for its fiscal fourth quarter and year ended December 20, 2009.

On a GAAP basis, fourth-quarter net income totaled $1.3 million, or $0.04 per diluted share, on revenue of $299.7 million. This compares with a net loss of $20.3 million, or $0.67 per diluted share on revenue of $314.7 million for the same period a year ago. Adjusted fourth-quarter 2009 net income totaled $3.7 million, or $0.12 per diluted share, after excluding charges for antitrust-related legal expenses and for a voluntary separation program for certain union employees and tax adjustments totaling $2.4 million, or $0.08 per share. Adjusted net income for the 2008 fourth quarter totaled $1.2 million, or $0.04 per diluted share, which excluded antitrust-related legal fees, and impairment and restructuring charges totaling $32.4 million pre-tax, or $0.71 per share after tax adjustments.

Comparison of GAAP and Non-GAAP Earnings (in millions, except per share data)*

	Quarter Ended					Fiscal Year Ended
	12/20/09		12/21/08			12/20/09			12/21/08
GAAP:
Operating revenue	$	299.7	$	314.7		$	1,158.5		$	1,304.3
Net income (loss)(1)	$	1.3	$	(20.3	)	$	(31.3	)	$	(2.6	)
Net income (loss) per diluted share(1)	$	0.04	$	(0.67	)	$	(1.03	)	$	(0.09	)
Non-GAAP:
EBITDA	$	26.1	$	(7.7	)	$	77.3		$	89.9
Adjusted EBITDA*	$	28.2	$	24.7		$	112.7		$	130.0
Adjusted net income*	$	3.7	$	1.2		$	14.5		$	25.2
Adjusted net income per diluted share*	$	0.12	$	0.04		$	0.47		$	0.82

*	See attached schedules for reconciliation of fourth-quarter and fiscal year 2009 and 2008 reported GAAP results to Non-GAAP results.
(1)	Net income for the 2008 fourth-quarter and fiscal year is adjusted for retrospective application of changes in accounting for convertible notes and restricted stock share-based payment awards as participating securities.

Horizon Lines 4th Quarter 2009 Page 2 of 13

“Our company performed well in the fourth quarter, considering the continued challenging economic environment,” said Chuck Raymond, Chairman, President and Chief Executive Officer. “Our revenue remained under pressure from lower cargo volumes that were impacted by the ongoing economic challenges in our markets, but the rate of decline improved for the second consecutive quarter. We also maintained stable revenue per container, net of fuel, and generated increased revenue from our logistics business. We believe our market share held steady as we remained intensely focused on customer service, schedule integrity and cost management. Horizon Lines once again was recognized by some of the nation’s largest shippers as being best in class.

“For 2009, we produced adjusted free cash flow totaling $70.5 million, compared with $59.8 million for 2008,” Mr. Raymond continued. “We used the cash generated in the fourth quarter to voluntarily repay $36.5 million of debt, which followed voluntary payments of $10 million in the third quarter and $5 million in the second quarter. As a result, we ended the year with $28 million less in funded debt than at year end 2008.”

Horizon Lines also announced that its Board of Directors voted at its regularly scheduled meeting yesterday to declare a quarterly cash dividend of $0.05 per share, payable on March 15, 2010, to stockholders of record on March 1, 2010. The decision to reduce the dividend to $0.05 from $0.11 per share will preserve approximately $7.3 million of cash on an annualized basis.

“We believe the revised dividend retains an attractive and appropriate payout to our stockholders, while at the same time giving management additional flexibility to augment our ongoing focus on debt reduction,” Mr. Raymond said.

Fourth-Quarter 2009 Financial Highlights

• Operating Revenue — Operating revenue declined 4.8% to $299.7 million from $314.7 million a year ago. The largest factor in the $15 million revenue decrease was a $9.3 million reduction related to volume, which fell 4.2% from the same period last year. Reduced fuel surcharges accounted for $7.8 million of the decline. The volume decrease was a result of continuing overall economic weakness that negatively impacted discretionary consumer spending across all tradelanes. Specifically, these factors included a slowdown in retail expansion and cautious consumer sentiment in Alaska, a decline in visitors and construction in Hawaii, and the ongoing recession in Puerto Rico. These declines were partially offset by a slight increase in rates, net of fuel, and cargo mix, and by revenue improvement in the company’s Logistics business. Logistics experienced strengthening volumes in its International Non-Vessel Operating Common Carrier business and its domestic Less-Than-Truckload freight brokerage business.

• Operating Income — GAAP operating income for the fourth quarter totaled $11.9 million, compared with a loss of $23.1 million for the fourth quarter of 2008. The 2009 GAAP operating income includes expenses of $2.1 million, consisting of $1.8 million in antitrust-related legal expenses and $0.3 million in union severance charges. The 2008 GAAP operating income includes $32.4 million in expenses comprised of $3.8 million in antitrust-related legal expenses, a $25.4 million impairment charge, and a $3.2 million restructuring charge. Excluding these items, adjusted operating income totaled $14.0

Horizon Lines 4th Quarter 2009 Page 3 of 13

	million for the fourth quarter of 2009, and $9.3 million for the prior year’s fourth quarter. The improvement from last year was largely due to non-union workforce reduction savings and other cost-containment efforts, as well as lower dry-dock amortization.
•	EBITDA — EBITDA totaled $26.1 million for the 2009 fourth quarter, compared with a loss of $7.7 million for the same period a year ago. Adjusted EBITDA for the fourth quarter of 2009 was $28.2 million, compared with $24.7 million for 2008. EBITDA and adjusted EBITDA for the 2009 and 2008 fourth quarters were impacted by the same factors affecting operating income.
•	Shares Outstanding — The company had a weighted daily average of 30.9 million diluted  shares outstanding for the fourth quarter of 2009, compared with 30.3 million for the fourth quarter of 2008.
•	Fiscal-Year Results — For the fiscal year ended December 20, 2009, operating revenue decreased 11.2% to $1.16 billion from $1.30 billion for 2008. EBITDA totaled $77.3 million compared with $89.9 million a year ago. Adjusted EBITDA was $112.7 million compared with $130.0 million a year ago. The 2009 net loss totaled $31.3 million, or $1.03 per diluted share, while adjusted net income totaled $14.5 million, or $0.47 per diluted share. For fiscal 2008, the net loss totaled $2.6 million, or $0.09 per diluted share, while adjusted net income was $25.2 million, or $0.82 per diluted share. Adjusted EBITDA and adjusted net income for 2009 exclude a $20.0 million charge related to the previously disclosed pending class-action legal settlement in Puerto Rico, $12.2 million in antitrust-related legal expenses, a $10.5 million tax valuation allowance, a $1.9 million impairment charge, a $1.0 million restructuring charge, and $0.3 million related to a voluntary separation program for certain union employees. Adjusted EBITDA and net income for 2008 exclude a $25.4 million impairment charge, $10.7 million in antitrust-related legal expenses, a $3.2 million restructuring charge, and $0.8 million related to a voluntary separation program for certain union employees.

Please see attached schedules for the reconciliation of fourth-quarter and fiscal-year 2009 and 2008 reported GAAP results and Non-GAAP adjusted results.

Outlook

“We expect conditions in the markets where we operate to remain challenging in 2010,” Mr. Raymond said. “Some of our market economies are beginning to exhibit possible signs of modest recovery, which could be further fueled by the federal economic stimulus program. While we see the potential for volume stabilization and slight rate improvement given this scenario, we also expect ongoing fuel price volatility and increased contractual labor costs and benefits assessments through 2010. Based on these expectations, we will continue to aggressively manage costs, liquidity, and cash flow as we move forward.”

Webcast & Conference Call Information

Company executives will provide additional perspective on the company’s financial results during a conference call beginning at 11:00 a.m. Eastern Time today. Those interested in

Horizon Lines 4th Quarter 2009 Page 4 of 13

participating in the call may do so by dialing 1-866-394-6819, and providing the operator with conference number 50331482. A copy of the presentation materials may be printed from the Horizon Lines website, http://www.horizonlines.com, shortly before the start of the call. Alternatively, a live audio webcast of the call may be accessed at http://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.

Use of Non-GAAP Measures

Horizon Lines reports its financial results in accordance with U.S. generally accepted accounting principles (GAAP). The company also believes that the presentation of certain non-GAAP measures, i.e., EBITDA, free cash flow and results excluding certain costs and expenses, provides useful information for the understanding of its ongoing operations and enables investors to focus on period-over-period operating performance without the impact of significant special items. The company further feels these non-GAAP measures enhance the user’s overall understanding of the company’s current financial performance relative to past performance and provide a better baseline for modeling future earnings expectations. Non-GAAP measures are reconciled in the financial tables accompanying this news release. The company cautions that non-GAAP measures should be considered in addition to, but not as a substitute for, the company’s reported GAAP results.

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 20 U.S.-flag containerships and operates five 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, using information technology developed by Horizon Services Group and intermodal trucking and warehousing services provided by Sea-Logix. Transportation offerings include international ocean intermediary services and North American LTL and trucking networks. 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.

Horizon Lines 4th Quarter 2009 Page 5 of 13

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 to be filed with the SEC on or about February 4, 2010, 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.

(Tables Follow)

Horizon Lines 4th Quarter 2009 Page 6 of 13

Horizon Lines, Inc.
Unaudited Condensed Consolidated Balance Sheets
(in thousands, except per share data)

				December 21,
	December 20,			2008
	2009			(As Adjusted)(1)
Assets
Current assets
Cash	$	6,419		$	5,487
Accounts receivable, net of allowance of $7,578 and $8,217 at December 20, 2009 and December 21, 2008, respectively		123,536			135,020
Prepaid vessel rent		4,580			4,471
Materials and supplies		30,254			23,644
Deferred tax asset		2,929			7,450
Other current assets		9,027			10,703
Total current assets		176,745			186,775
Property and equipment, net		193,438			208,453
Goodwill		317,068			317,068
Intangible assets, net		105,405			125,542
Deferred tax asset		—			10,669
Other long-term assets		25,854			24,122
Total assets	$	818,510		$	872,629
Liabilities and Stockholders’ Equity
Current liabilities
Accounts payable	$	43,257		$	41,947
Current portion of long-term debt		18,750			6,552
Accrued vessel rent		4,339			5,421
Other accrued liabilities		110,473			97,720
Total current liabilities		176,819			151,640
Long-term debt, net of current portion		496,105			526,259
Deferred rent		22,585			27,058
Deferred tax liability		4,248			—
Other long-term liabilities		17,475			30,836
Total liabilities		717,232			735,793
Stockholders’ equity
Preferred stock, $.01 par value, 30,500 shares authorized; no shares issued or outstanding		—			—
Common stock, $.01 par value, 100,000 shares authorized, 34,091 shares issued and 30,291 shares outstanding as of December 20, 2009 and 33,808 shares issued and 30,008 shares outstanding as of December 21, 2008		341			338
Treasury stock, 3,800 shares at cost		(78,538	)		(78,538	)
Additional paid in capital		196,900			199,644
(Accumulated deficit) retained earnings		(15,874	)		22,094
Accumulated other comprehensive loss		(1,551	)		(6,702	)
Total stockholders’ equity		101,278			136,836
Total liabilities and stockholders’ equity	$	818,510		$	872,629

(1) Results are adjusted for retrospective application of changes in accounting for convertible notes and restricted stock share-based payment awards as participating securities.

Horizon Lines 4th Quarter 2009 Page 7 of 13

Horizon Lines, Inc.
Unaudited Condensed Consolidated Statements of Income
(in thousands, except per share data)

	Fiscal Quarters Ended					Fiscal Years Ended
			December 21,						December 21,
	December 20,		2008			December 20,			2008
	2009		(As Adjusted)(1)			2009			(As Adjusted)(1)
Operating revenue	$	299,674	$	314,715		$	1,158,481		$	1,304,259
Operating expense:
Cost of services (excluding depreciation expense)		250,551		265,606			954,915			1,074,675
Depreciation and amortization		11,441		11,318			44,866			45,643
Amortization of vessel dry-docking		2,758		3,994			13,694			17,162
Selling, general and administrative		22,721		27,689			102,231			108,206
Settlement of class action lawsuit		—		—			20,000			—
Restructuring charge		—		3,244			1,001			3,244
Impairment charge		—		25,415			1,867			25,415
Miscellaneous expense, net		295		506			1,069			2,898
Total operating expense		287,766		337,772			1,139,643			1,277,243
Operating income (loss)		11,908		(23,057	)		18,838			27,016
Other expense:
Interest expense, net		10,426		9,871			39,675			41,399
Loss on modification of debt		—		—			50			—
Other expense (income), net		8		(59	)		18			(62	)
Income (loss) before income tax expense		1,474		(32,869	)		(20,905	)		(14,321	)
Income tax expense (benefit)		148		(12,613	)		10,367			(11,728	)
Net income (loss)	$	1,326	$	(20,256	)	$	(31,272	)	$	(2,593	)
Net income (loss) per share:
Basic	$	0.04	$	(0.67	)	$	(1.03	)	$	(0.09	)
Diluted	$	0.04	$	(0.67	)	$	(1.03	)	$	(0.09	)
Number of shares used in calculation:
Basic		30,484		30,338			30,451			30,278
Diluted		30,942		30,338			30,451			30,278
Dividends declared per common share	$	0.11	$	0.11		$	0.44		$	0.44

(1) Results are adjusted for retrospective application of changes in accounting for convertible notes and restricted stock share-based payment awards as participating securities.

Horizon Lines 4th Quarter 2009 Page 8 of 13

Horizon Lines, Inc.
Unaudited Condensed Consolidated Statements of Cash Flows
(in thousands)

	Fiscal Years Ended
				December 21,
	December 20,			2008
	2009			(As Adjusted)(1)
Cash flows from operating activities:
Net loss	$	(31,272	)	$	(2,593	)
Adjustments to reconcile net loss to net cash provided by operating activities:
Depreciation		24,235			24,343
Amortization of other intangible assets		20,631			21,300
Amortization of vessel dry-docking		13,694			17,162
Impairment charge		1,867			25,415
Restructuring charge		1,001			3,244
Amortization of deferred financing costs		2,947			2,693
Deferred income taxes		10,396			(12,985	)
Gain on equipment disposals		(154	)		(24	)
Loss on modification of debt		50			—
Stock-based compensation		3,096			3,651
Accretion of interest on 4.25% convertible notes		10,011			8,901
Changes in operating assets and liabilities:
Accounts receivable, net		11,763			5,854
Materials and supplies		(6,739	)		7,636
Other current assets		1,245			23
Accounts payable		1,310			1,625
Accrued liabilities		16,515			(2,721	)
Vessel rent		(4,874	)		(4,883	)
Vessel dry-docking payments		(14,735	)		(13,913	)
Other assets/liabilities		(3,489	)		4,640
Net cash provided by operating activities		57,498			89,368
Cash flows from investing activities:
Purchases of equipment		(13,050	)		(39,149	)
Purchase of business		—			(198	)
Proceeds from the sale of equipment		1,237			500
Net cash used in investing activities		(11,813	)		(38,847	)
Cash flows from financing activities:
Borrowing under revolving credit facility		64,000			78,000
Payments on revolving credit facility		(84,000	)		(80,000	)
Payments on long-term debt		(7,968	)		(6,538	)
Dividends to stockholders		(13,397	)		(13,273	)
Payments of financing costs		(3,492	)		(139	)
Common stock issued under employee stock purchase plan		104			38
Purchase of treasury stock		—			(29,330	)
Payments on capital lease obligation		—			(81	)
Proceeds from exercise of stock options		—			13
Net cash used in financing activities		(44,753	)		(51,310	)
Net increase (decrease) in cash		932			(789	)
Cash at beginning of year		5,487			6,276
Cash at end of year	$	6,419		$	5,487

(1) Results are adjusted for retrospective application of changes in accounting for convertible notes and restricted stock share-based payment awards as participating securities.

Horizon Lines 4th Quarter 2009 Page 9 of 13

Horizon Lines, Inc.
Adjusted Operating Income Reconciliation
($ in Millions)

	Quarter Ended		Quarter Ended			Year Ended		Year Ended
	December 20, 2009		December 21, 2008			December 20, 2009		December 21, 2008
Operating Income (Loss)	$	11.9	$	(23.1	)	$	18.8	$	27.0
Adjustments:
Legal Settlement		—		—			20.0		—
Anti-Trust Legal Expenses		1.8		3.8			12.2		10.7
Impairment Charge		—		25.4			1.9		25.4
Restructuring Charge		—		3.2			1.0		3.2
OPEIU Severance		0.3		—			0.3		0.8
Total Adjustments		2.1		32.4			35.4		40.1
Adjusted Operating Income	$	14.0	$	9.3		$	54.2	$	67.1

Horizon Lines 4th Quarter 2009 Page 10 of 13

Horizon Lines, Inc.
Adjusted Net Income Reconciliation
($ in Millions)

	Quarter Ended		Quarter Ended			Year Ended			Year Ended
	December 20, 2009		December 21, 2008			December 20, 2009			December 21, 2008
Net Income (Loss) (1)	$	1.3	$	(20.3	)	$	(31.3	)	$	(2.6	)
Adjustments:
Legal Settlement		—		—			20.0			—
Anti-Trust Legal Expenses		1.8		3.8			12.2			10.7
Impairment Charge		—		25.4			1.9			25.4
Restructuring Charge		—		3.2			1.0			3.2
OPEIU Severance		0.3		—			0.3			0.8
Tax Adjustments		0.3		(10.9	)		(0.1	)		(12.3	)
Tax Valuation Allowance		—		—			10.5			—
Total Adjustments		2.4		21.5			45.8			27.8
Adjusted Net Income	$	3.7	$	1.2		$	14.5		$	25.2

(1) 2008 results are adjusted for retrospective application of changes in accounting for convertible notes.

Horizon Lines 4th Quarter 2009 Page 11 of 13

Horizon Lines, Inc.
Adjusted Net Income Per Diluted Share Reconciliation

	Quarter Ended		Quarter Ended			Year Ended			Year Ended
	December 20, 2009		December 21, 2008			December 20, 2009			December 21, 2008
Net Income (Loss) Per Diluted Share (1)	$	0.04	$	(0.67	)	$	(1.03	)	$	(0.09	)
Adjustments Per Share:
Legal Settlement		—		—			0.66			—
Anti-Trust Legal Expenses		0.06		0.13			0.40			0.35
Impairment Charge		—		0.84			0.06			0.84
Restructuring Charge		—		0.11			0.03			0.11
Loss on Modification of Debt		—		—			—			—
OPEIU Severance		0.01		—			0.01			0.03
Tax Adjustments		0.01		(0.37	)		—			(0.42	)
Tax Valuation Allowance		—		—			0.34			—
Total Adjustments		0.08		0.71			1.50			0.91
Adjusted Net Income Per Diluted Share	$	0.12	$	0.04		$	0.47		$	0.82

(1) 2008 results are adjusted for retrospective application of changes in accounting for convertible notes and restricted stock share-based payment awards as participating securities.

Horizon Lines 4th Quarter 2009 Page 12 of 13

Horizon Lines, Inc.
EBITDA and Adjusted EBITDA Reconciliation
($ in Millions)

	Quarter Ended		Quarter Ended			Year Ended			Year Ended
	December 20, 2009		December 21, 2008			December 20, 2009			December 21, 2008
Net Income (Loss) (1)	$	1.3	$	(20.3	)	$	(31.3	)	$	(2.6	)
Interest Expense, Net		10.4		9.9			39.7			41.4
Tax Expense		0.2		(12.6	)		10.4			(11.7	)
Depreciation and Amortization		14.2		15.3			58.5			62.8
EBITDA		26.1		(7.7	)		77.3			89.9
Legal Settlement		—		—			20.0			—
Anti-Trust Legal Fees		1.8		3.8			12.2			10.7
Impairment Charge		—		25.4			1.9			25.4
Restructuring Charge		—		3.2			1.0			3.2
OPEIU Severance		0.3		—			0.3			0.8
Adjusted EBITDA	$	28.2	$	24.7		$	112.7		$	130.0

(1) 2008 results are adjusted for retrospective application of changes in accounting for convertible notes.

Note: EBITDA is defined as net income (loss) 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 the Company 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. Adjusted EBITDA excludes certain charges in order to evaluate our operating performance, for making day-to-day operating decisions and when determining the payment of discretionary bonuses.

Horizon Lines 4th Quarter 2009 Page 13 of 13

Horizon Lines, Inc.
EBITDA and Adjusted EBITDA Segment Reconciliation
($ in Millions)

Fiscal Fourth Quarter 2009

	Liner		Logistics			Consolidated
Operating Income (Loss)	$	13.3	$	(1.4	)	$	11.9
Depreciation and Amortization		11.2		0.2			11.4
Amortization of Vessel Dry-docking		2.8		—			2.8
EBITDA		27.3		(1.2	)		26.1
Anti-Trust Legal Expenses		1.8		—			1.8
OPEIU Severance		0.3		—			0.3
Adjusted EBITDA	$	29.4	$	(1.2	)	$	28.2

Horizon Lines, Inc.
EBITDA and Adjusted EBITDA Segment Reconciliation
($ in Millions)

Fiscal Year 2009

	Liner		Logistics			Consolidated
Operating Income (Loss)	$	27.3	$	(8.5	)	$	18.8
Depreciation and Amortization		44.2		0.6			44.8
Amortization of Vessel Dry-docking		13.7		—			13.7
EBITDA		85.2		(7.9	)		77.3
Legal Settlement		20.0		—			20.0
Anti-Trust Legal Expenses		12.2		—			12.2
Impairment Charge		1.9		—			1.9
Restructuring Charge		0.8		0.2			1.0
OPEIU Severance		0.3		—			0.3
Adjusted EBITDA	$	120.4	$	(7.7	)	$	112.7

# # #