Exhibit 5.1

[Dorsey & Whitney LLP Letterhead]

July 19, 2012

SUPERVALU INC.

7075 Flying Cloud Drive

Eden Prairie, Minnesota 55344

Re: Registration Statement on Form S-8

Ladies and Gentlemen:

We have acted as counsel to SUPERVALU INC., a Delaware corporation (the “Company”), in connection with a Registration Statement on Form S-8 (the “Registration Statement”) relating to the registration of the offer and sale by the Company of up to 47,600,000 shares of the Company’s common stock, par value $0.01 per share (the “Shares”) issuable pursuant to the SUPERVALU INC. 2012 Stock Plan and the SUPERVALU INC. Directors’ Deferred Compensation Plan (2009 Statement), as amended (collectively, the “Plans”).

We have examined such documents and have reviewed such questions of law as we have considered necessary and appropriate for the purposes of the opinions set forth below. We have assumed the authenticity of all documents submitted to us as originals, the genuineness of all signatures and the conformity to authentic originals of all documents submitted to us as copies. We have also assumed the legal capacity for all purposes relevant hereto of all natural persons. As to questions of fact material to our opinions, we have relied upon certificates of officers of the Company and of public officials.

Based on the foregoing, we are of the opinion that the Shares have been duly authorized and, upon issuance, delivery and payment therefor in accordance with the terms of the Plans and any relevant agreements thereunder, will be validly issued, fully paid and nonassessable.

Our opinions expressed above are limited to the Delaware General Corporation Law.

We hereby consent to the filing of this opinion as an exhibit to the Registration Statement.

Very truly yours,

/s/ Dorsey & Whitney LLP

GLT