Exhibit 5.1

December 20, 2023 United Natural Foods, Inc. 313 Iron Horse Way Providence, Rhode Island 02908 Mayer Brown LLP 71 South Wacker Drive
Chicago, IL 60606
United States of America T: +1 312 782 0600 F: +1 312 701 7711 www.mayerbrown.com

Re: 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 the offer and sale of up to 3,700,000 shares of the Company’s Common Stock, par value $0.01 per share (the “Shares”), pursuant to the Company’s Third Amended and Restated 2020 Equity Incentive Plan (the “Plan”), as described in the Form S-8 Registration Statement (the “Registration Statement”) filed with the Securities and Exchange Commission (the “Commission”) on the date hereof.

As counsel to the Company, we have examined originals or copies certified or otherwise identified to our satisfaction of the Company’s certificate of incorporation and the Company’s bylaws, each as amended, restated and supplemented, the resolutions of the board of directors of the Company and such records of the Company, certificates and other documents and such questions of law as we considered necessary or appropriate for purposes of this opinion. As to certain factual matters, we have relied, to the extent we deem such reliance proper, upon certificates of public officials and officers of the Company. In rendering this opinion, we have assumed the genuineness of all signatures, the authenticity of all documents submitted to us as originals and the conformity to authentic original documents of all documents submitted to us as copies.

Subject to the foregoing, we are of the opinion that the Shares have been duly authorized for issuance and, when issued in conformity with the provisions of the Plan and for such consideration as shall be determined from time to time by the board of directors of the Company, or by the compensation committee thereof, will be validly issued, fully paid and nonassessable.

The opinion expressed above is limited to the Delaware General Corporation Law and we express no opinion with respect to any other laws.

We consent to your filing this opinion as an exhibit to the Registration Statement.  In giving such consent, we do not thereby 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 Commission thereunder.

Very truly yours,

/s/ Mayer Brown LLP

Mayer Brown is a global services provider comprising an association of legal practices that are separate entities including
Mayer Brown LLP (Illinois, USA), Mayer Brown International LLP (England), Mayer Brown (a Hong Kong partnership)
and Tauil & Chequer Advogados (a Brazilian partnership).