Exhibit 5.1

May 19, 2016

US Foods Holding Corp.

9399 W. Higgins Road, Suite 500

Rosemont, IL 60018

Ladies and Gentlemen:

This opinion letter is furnished to you in connection with your Registration Statement on Form S-1 (File Number 333-209442), initially filed with the Securities and Exchange Commission under the Securities Act of 1933, as amended (the “Securities Act”), on February 9, 2016, (such Registration Statement, as amended or supplemented, the “Registration Statement”), relating to the registration of the offer and sale of up to 51,111,111 shares of common stock, par value $0.01 per share, including up to 6,666,667 shares to cover over-allotments, (all such shares, together with any additional shares registered pursuant to Rule 462(b) under the Securities Act, the “Shares”) of US Foods Holding Corp., a Delaware corporation (the “Company”), pursuant to the underwriting agreement (the “Underwriting Agreement”) to be entered into by and among the Company and Goldman, Sachs & Co., Morgan Stanley & Co. LLC and J.P. Morgan Securities LLC, as representative of the several underwriters, in the substantially the form filed as an exhibit to the Registration Statement.

We have examined the Registration Statement, and the Company’s Amended and Restated Certificate of Incorporation in the form filed as Exhibit 3.1 to the Registration Statement and the Company’s Amended and Restated Bylaws in the form filed as Exhibit 3.2 to the Registration Statement. We also have examined the originals, or duplicates or certified or conformed copies, of such records, agreements, documents and other instruments and have made such other investigations as we have deemed relevant and necessary in connection with the opinions hereinafter set forth. As to questions of fact material to this opinion, we have relied upon certificates or comparable documents of public officials and of officers and representatives of the Company.

In all such investigations and examinations, we have assumed the legal capacity of all natural persons, the genuineness of all signatures, the authenticity of original and certified documents and the conformity to original or certified documents of all copies submitted to us as conformed or reproduction copies.

In connection with our opinions expressed below, we have assumed that (A) the Pricing Committee of the Board of Directors of the Company has taken all necessary corporate action to authorize and approve the issuance of the Shares, (B) the Certificate of Amendment to the Certificate of Incorporation has been duly filed with the Secretary of State of the State of Delaware and (C) payment and delivery in accordance with the applicable definitive Underwriting Agreement approved by the Pricing Committee of the Board of Directors of the Company.

Based on the foregoing and subject to the limitations, qualifications and assumptions set forth herein, we are of the opinion that, the Shares to be issued and sold by the Company pursuant to the Registration Statement will be duly authorized and, when such Shares are issued and paid for in accordance with the terms of the Underwriting Agreement, will be validly issued, fully paid and nonassessable.

The foregoing opinions is based exclusively on the General Corporation Law of the State of Delaware.

We consent to the filing of this opinion as an exhibit to the Registration Statement and to the reference to us under the heading “Legal Matters” in the Registration Statement, the Prospectus constituting a part thereof and any amendments thereto.

Sincerely,

/s/ Jenner & Block LLP

JENNER & BLOCK LLP