Exhibit 5.1

WRITER’S DIRECT LINE   WEIL, GOTSHAL & MANGES LLP   SILICON VALLEY OFFICE   201 REDWOOD SHORES PARKWAY   REDWOOD SHORES, CALIFORNIA 94065   (650) 802-3000   FAX: (650) 802-3100     August 27, 2007   AUSTIN   BOSTON   BRUSSELS   BUDAPEST   DALLAS   FRANKFURT   HOUSTON   LONDON   MIAMI   MUNICH   NEW YORK   PARIS   PRAGUE   PROVIDENCE   SHANGHAI   SINGAPORE   WARSAW   WASHINGTON, D.C.

Core-Mark Holding Company, Inc.

395 Oyster Point Boulevard

Suite 415

South San Francisco, CA 94080

Ladies and Gentlemen:

We have acted as counsel to Core-Mark Holding Company, Inc., a Delaware corporation (the “Company”), in connection with the preparation and filing of the Company’s Registration Statement on Form S-8 under the Securities Act of 1933, as amended (the “Registration Statement”), relating to the registration of up to 1,202,350 shares of the Company’s common stock, par value $0.01 per share (the “Common Stock”), which may be issued by the Company following the filing of the Registration Statement pursuant to the Company’s 2007 Long Term Incentive Plan (the “Plan”).

In so acting, we have examined originals or copies (certified or otherwise identified to our satisfaction) of the Registration Statement, the Plan and such corporate records, agreements, documents and other instruments, and such certificates or comparable documents of public officials and of officers and representatives of the Company, and have made such inquiries of such officers and representatives, as we have deemed relevant and necessary as a basis for the opinion hereinafter set forth.

In such examination, we have assumed the genuineness of all signatures, the legal capacity of all natural persons, the authenticity of all documents submitted to us as originals, the conformity to original documents of documents submitted to us as certified, conformed or photostatic copies and the authenticity of the originals of such latter documents. As to all questions of fact material to this opinion that have not been independently established, we have relied upon certificates or comparable documents of officers and representatives of the Company.

Based on the foregoing, and subject to the qualifications stated herein, we are of the opinion that the 1,202,350 shares of Common Stock being registered for sale pursuant to the Registration Statement have been duly authorized, and when issued and delivered upon receipt by the Company of consideration constituting lawful consideration under Delaware law in accordance with the Plan, will be validly issued, fully paid and non-assessable.

Core-Mark Holding Company, Inc.

August 27, 2007

Page 2

The opinion expressed herein is limited to the corporate laws of the State of Delaware, and we express no opinion as to the effect on matters covered by this letter of the laws of any other jurisdiction.

We hereby consent to the filing of a copy of this opinion letter as an exhibit to the Registration Statement and to any and all references to our firm in the Registration Statement.

Very truly yours,

/S/    WEIL, GOTSHAL & MANGES LLP        

Weil, Gotshal & Manges LLP

2