Exhibit 5.1

Weil, Gotshal & Manges LLP

201 Redwood Shores Parkway    

Redwood Shores, CA 94065-1134

+1 650 802 3000 tel

+1 650 802 3100 fax

May 24, 2019

Core-Mark Holding Company, Inc.

1500 Solana Blvd., Suite 3400

Westlake, Texas 76262

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 Post-Effective Amendment No. 1 (the “Amendment”) to the Company’s Registration Statement on Form S-8 filed on December 19, 2014 (the “Registration Statement”) under the Securities Act of 1933, as amended (the “Securities Act”), relating to the 1,923,862 shares of the Company’s common stock, par value $0.01 per share (the “Common Stock”) that remain available for grant under the Core-Mark Holding Company, Inc. 2010 Long-Term Incentive Plan (as amended, the “2010 LTIP”) as of March 18, 2019, and 713,097 shares representing the maximum number of shares that may be forfeited under the 2010 LTIP, that will be available for award grant purposes following the filing of the Amendment, under the Core-Mark Holding Company, Inc. 2019 Long-Term Incentive Plan (the “2019 LTIP”) (collectively, such 2,636,959 shares of Common Stock referred to herein as the “Rollover Shares”).

In so acting, we have examined originals or copies (certified or otherwise identified to our satisfaction) of (i) the Amendment; (ii) the Registration Statement; (iii) the 2019 LTIP; (iv) the 2010 LTIP and all amendments thereto; and (v) 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 all 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 Rollover Shares that will be available for award grant purposes following the filing of the Amendment under the 2019 LTIP have been duly authorized and, when issued and delivered in accordance with the 2019 LTIP and the Amendment, will be validly issued, fully paid and non-assessable.

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 Amendment. In giving such consent we do not hereby admit that we are in the category of persons whose consent is required under Section 7 of the Securities Act of 1933, as amended, or the rules and regulations of the Securities and Exchange Commission.

Very truly yours,

/S/    Weil, Gotshal & Manges LLP

Weil, Gotshal & Manges LLP