Exhibit 5.1

December 18, 2019

United Natural Foods, Inc.

313 Iron Horse Way

Providence, RI 02908

Re: United Natural Foods, Inc.

Registration Statement on Form S-8

Ladies and Gentlemen:

We have acted as special counsel to United Natural Foods, Inc., a Delaware corporation (the “Company”), in connection with its filing with the Securities and Exchange Commission (the “Commission”) of a registration statement on Form S-8 (the “Registration Statement”) under the Securities Act of 1933 (the “Securities Act”), on the date hereof. The Registration Statement relates to the registration by the Company of 7,200,000 shares (the “Plan Shares”) of the Company’s common stock, par value $0.01 per share (the “Common Stock”), issuable pursuant to the United Natural Foods, Inc. 2020 Equity Incentive Plan (the “Plan”). This opinion is being furnished in accordance with the requirements of Item 601(b)(5) of Regulation S-K under the Securities Act.

In rendering the opinions stated herein, we have examined and relied upon the following:

(a)the Registration Statement in the form filed with the Commission on the date hereof;

(b)an executed copy of a certificate of Jill E. Sutton, Chief Legal Officer, General Counsel and Corporate Secretary of the Company, dated the date hereof (the “Officer’s Certificate”);

(c)the Plan, certified pursuant to the Officer’s Certificate;

(d)a copy of the Company’s Amended and Restated Certificate of Incorporation certified by the Secretary of State of the State of Delaware as of December 16, 2019, certified pursuant to the Officer’s Certificate;

(e)a copy of the Company’s Fourth Amended and Restated Bylaws, in effect as of the date hereof, certified pursuant to the Officer’s Certificate; and

(f)a copy of certain resolutions of the Board of Directors of the Company, adopted on September 26, 2019, certified pursuant to the Officer’s Certificate.

We have also examined originals or copies, certified or otherwise identified to our satisfaction, of such records of the Company and such agreements, certificates and receipts of public officials, certificates of officers or other representatives of the Company and others, and such other documents as we have deemed necessary or appropriate as a basis for the opinions stated below.

In our examination, we have assumed the genuineness of all signatures, including endorsements, the legal capacity and competency 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 facsimile, electronic, certified or photostatic copies, and the authenticity of the originals of such copies. As to any facts relevant to the opinions stated herein that we did not independently establish or verify, we have relied upon statements and representations of officers and other representatives of the Company and others and of public officials, including those in the Officer’s Certificate.

In rendering the opinion stated herein, we have also assumed that (i) an appropriate account statement regarding the Plan Shares credited to a recipient’s account maintained with the Company’s transfer agent has been or will be issued by the Company’s transfer agent, (ii) the issuance of the Plan Shares will be properly recorded in the books and records of the Company, (iii) each stock option, restricted share award, restricted stock unit award and performance share unit award or other award pursuant to which Plan Shares may be issuable, is, or will be, as the case may be, consistent with the Plan and will be duly authorized, executed and delivered by the parties thereto and (iv) the consideration received by the Company for each of the Plan Shares delivered pursuant to the Plan shall not be less than the per share par value of the Plan Shares.

We do not express any opinion with respect to the laws of any jurisdiction other than the General Corporation Law of the State of Delaware (the “DGCL”).

Based upon the foregoing and subject to the qualifications and assumptions stated herein, we are of the opinion that the Plan Shares have been duly authorized by all requisite corporate action on the part of the Company under the DGCL and when the Plan Shares are issued, delivered and paid for in accordance with the terms and conditions of the Plan and any applicable award agreement, the Plan Shares will be validly issued, fully paid and nonassessable.

We hereby consent to the filing of this opinion with the Commission as an exhibit to the Registration Statement. In giving this consent, we do not thereby admit that we are within the category of persons whose consent is required under Section 7 of the Securities Act or the General Rules and Regulations under the Securities Act.

Very truly yours,

/s/ Cohen & Gresser LLP