Exhibit 99.1

Core-Mark Sales up 9% for the first quarter of 2006

South San Francisco, California – May 19, 2006 – Core-Mark Holding Company, Inc. (Nasdaq: CORE), announced its financial results for the first quarter ended March 31, 2006. Net sales for the first quarter of 2006 were $1.2 billion compared to $1.1 billion for the first quarter of 2005, a 9% increase. Excise taxes, included in net sales were $280 million for the first quarter 2006 and $262 million for the first quarter of 2005.

Three months ended March 31, 2006 Financial Results – A Summary

Core-Mark reported today net income of $1.7 million or $0.16 per fully diluted share for the first quarter of 2006. This compares with first quarter 2005 net income of $70 thousand or $0.01 per fully diluted share.

Net sales for the first quarter of 2006 were $1.2 billion, compared to $1.1 billion for the same period in 2005. Income from operations for each of the three months ended March 31, 2005 and 2006 were $3.9 million. The results for the three months ended March 31, 2006 included a pre-tax benefit of $1.1 million due to favorable settlements related to vendor and customer receivables, $0.6 million in cigarette holding profits and a LIFO expense of $1.4 million. The results for the three months ended March 31, 2005 included a pre-tax benefit of $1.0 million related to an unanticipated insurance recovery, $2.5 million in cigarette holding profits and a LIFO expense of $1.6 million.

Interest expense for the first quarter of 2006 was $0.7 million compared to $3.2 million for the first quarter of 2005, a decrease due primarily to the lower interest rates under the Company’s new debt facility and a reduction in borrowing. As of March 31, 2006, the Company had $37.0 million in long-term debt and $55.0 million in letters of credit outstanding. The Company’s long-term debt was $59.6 million and $51.9 million in letters of credit were outstanding as of December 31, 2005.

Guidance

Management reaffirmed that it currently expects to achieve net sales of approximately $5.0 billion in 2006. This forecast assumes no new national account wins or losses, additional excise tax increases nor net sales increases as a result of any acquisitions.

Our capital expenditure plan, also reaffirmed, is expected to total approximately $16 million for 2006, which assumes no acquisitions. The increase in planned capital expenditures from 2005 is based primarily on our plan to replace one of our older distribution centers and planned investment in new refrigerated equipment.

Investors Conference Call

We invite any interested investors to join us for our investor conference call Wednesday May 24, 2006 at 9 a.m. Pacific (noon Eastern) to discuss these results.

To participate in the call please dial 1-866-877-3102 from the US and Canada and follow the operator’s instructions. Callers outside the US and Canada should dial 706-679-6987. The conference call code is 9451587. To access the live webcast, log onto Core-Mark’s web site at www.core-mark.com and then select the investor relations section. Participants should log on at least 5 minutes before the call begins.

The call will be available for replay for two weeks after the completion of the event. The replay will be available starting May 24, 2006 at 12:00 noon Pacific by dialing 1-800-642-1687 or investors can replay the webcast by visiting www.core-mark.com under the investor relations section.

# # #

About Core-Mark

Core-Mark is one of the largest broad-line, full-service wholesale distributors of packaged consumer products to the convenience retail industry in North America. Founded in 1888, Core-Mark provides distribution and logistics services as well as marketing programs to over 19,000 retail locations in 38 states and five Canadian provinces through 24 distribution centers, two of which Core-Mark operate as third party logistics providers. Core-Mark services traditional convenience retailers, grocers, drug, liquor and specialty stores, and other stores that carry consumer packaged goods. For more information, please visit www.core-mark.com

Safe Harbor

This press release contains information constituting “forward-looking statements.” Forward-looking statements include all statements that do not relate solely to historical or current facts, and can generally be identified by the use of words such as “may,” “believe,” “will,” “expect,” “project,” “estimate,” “anticipate,” “plan”, “continue”, or other similar words. These forward-looking statements are based on the current plans, estimates and expectations of our management and are subject to certain risks and uncertainties that could cause actual results to differ materially from historical results or those anticipated. These factors include, but are not limited to: economic conditions affecting the cigarette and consumable goods industry; adverse effect of legislation and other matters affecting the cigarette industry; increased competition in the distribution industry; our inability to retain and attract customers; the negative affects of product liability claims; failure of our suppliers to provide products; increases in fuel prices; the loss of key personnel or our inability to attract and retain new qualified personnel; currency exchange rate fluctuations; and the negative effects of our reorganization on our customer, supplier and employee relationships. See the “Risk Factors” section included in our Form 10-K and other filings with the Securities and Exchange Commission for a discussion of certain risks that may affect our business.

These forward-looking statements speak only as of the date of this press release. We undertake no obligation to publicly update or revise any forward-looking statements, whether as a result of new information, future events or otherwise.

Contact: Milton Draper, Director of Investor Relations at 650-589-9445X3027 or mdraper@core-mark.com

CORE-MARK HOLDING COMPANY, INC. AND SUBSIDIARIES

CONDENSED CONSOLIDATED BALANCE SHEETS

(In millions, except share data)

(Unaudited)

	March 31, 2006			December 31, 2005
Assets
Current assets:
Cash and cash equivalents	$	19.8		$	30.0
Restricted cash		13.1			10.8
Accounts receivable, net of allowance for doubtful accounts of $6.1 and $6.5, respectively		130.6			128.6
Other receivables, net		25.1			27.2
Inventories, net		157.0			199.7
Deposits and prepayments		21.9			18.6
Total current assets		367.5			414.9
Property and equipment, net		40.5			40.9
Deferred income taxes		2.1			2.1
Other non-current assets, net		54.0			52.5
Total assets	$	464.1		$	510.4
Liabilities and Stockholders’ Equity
Current liabilities:
Accounts payable	$	47.0		$	46.3
Book overdrafts		6.8			20.2
Cigarette and tobacco taxes payable		53.8			64.0
Accrued liabilities		54.9			59.3
Income taxes payable		6.1			6.0
Deferred income taxes		13.2			13.3
Total current liabilities		181.8			209.1
Long-term debt, net		37.0			59.6
Other tax liabilities		3.9			3.9
Claims liabilities, net of current portion		41.2			41.0
Pension liabilities		12.2			12.2
Total liabilities		276.1			325.8
Commitments and Contingencies
Stockholders’ equity:
Common stock; $0.01 par value (50,000,000 shares authorized, 9,840,706 and 9,809,929 shares issued and outstanding at March 31, 2006 and December 31, 2005, respectively)		0.1			0.1
Additional paid-in capital		167.8			166.1
Retained earnings		21.3			19.6
Accumulated other comprehensive loss		(1.2	)		(1.2	)
Total stockholders’ equity		188.0			184.6
Total liabilities and stockholders’ equity	$	464.1		$	510.4

CORE-MARK HOLDING COMPANY, INC. AND SUBSIDIARIES

CONDENSED CONSOLIDATED STATEMENTS OF OPERATIONS

(In millions, except per share data)

(Unaudited)

	Three Months Ended March 31,
	2006		2005
Net sales	$	1,178.9	$	1,079.8
Cost of goods sold		1,114.4		1,016.8
Gross profit		64.5		63.0
Warehousing and distribution expenses		33.1		31.2
Selling, general and administrative expenses		27.2		27.6
Amortization of intangible assets		0.3		0.3
Total operating expenses		60.6		59.1
Income from operations		3.9		3.9
Interest expense, net		0.7		3.2
Foreign currency transaction losses, net		0.1		0.3
Amortization of debt issuance costs		0.1		0.3
Income before income taxes		3.0		0.1
Provision for income taxes		1.3		0.1
Net income	$	1.7	$	0.0
Basic income per common share	$	0.18	$	0.01
Diluted income per common share	$	0.16	$	0.01
Basic weighted average shares		9.8		9.8
Diluted weighted average shares		10.9		10.2

CORE-MARK HOLDING COMPANY, INC. AND SUBSIDIARIES

CONDENSED CONSOLIDATED STATEMENTS OF CASH FLOWS

(In millions)

(Unaudited)

	Three Months Ended March 31,
	2006			2005
Cash flows from operating activities:
Net income	$	1.7		$	0.0
Adjustments to reconcile net income to net cash provided by operating activities:
LIFO and inventory reserves		1.6			1.8
Amortization of stock-based compensation expense		1.1			1.0
Allowance for doubtful accounts		(0.8	)		0.5
Depreciation and amortization		2.9			3.3
Foreign currency transaction losses, net		0.1			0.3
Deferred income taxes		(0.1	)		—
Changes in operating assets and liabilities:
Accounts receivable		(2.1	)		(2.5	)
Other receivables		3.0			9.4
Inventories		41.3			10.6
Deposits, prepayments and other non-current assets		(5.8	)		(0.3	)
Accounts payable		0.7			(0.5	)
Cigarette and tobacco taxes payable		(10.3	)		8.7
Pension, claims and other accrued liabilities and income taxes payable		(4.1	)		(8.6	)
Net cash provided by operating activities		29.2			23.7
Cash flows from investing activities:
Restricted cash		(2.3	)		(2.0	)
Additions to property and equipment, net		(1.5	)		(1.5	)
Net cash used in investing activities		(3.8	)		(3.5	)
Cash flows from financing activities:
Borrowings under 2004 revolving credit facility, net		—			1.1
Repayments under 2005 revolving credit facility, net		(22.6	)		—
Principal payments on long-term debt		—			(10.0	)
Cash proceeds from exercise of common stock options		0.4			—
Excess tax deductions associated with stock-based compensation		0.2			—
Decrease in book overdrafts		(13.4	)		(3.8	)
Net cash used in financing activities		(35.4	)		(12.7	)
Effects of changes in foreign exchange rates		(0.2	)		(0.3	)
Increase (decrease) in cash and cash equivalents		(10.2	)		7.2
Cash and cash equivalents, beginning period		30.0			26.1
Cash and cash equivalents, end of period	$	19.8		$	33.3
Supplemental disclosures:
Cash paid during the period for:
Income Taxes	$	1.0		$	1.3
Interest	$	1.1		$	3.4