EXHIBIT 5.1

March 27, 2013

Wal-Mart Stores, Inc.

702 S.W. 8^th Street

Bentonville, Arkansas 72716

Re: Wal-Mart Stores, Inc.

Registration Statement on Form S-8 relating to the Walmart 401(k) Plan

Ladies and Gentlemen:

We have acted as special counsel for Wal-Mart Stores, Inc., a Delaware corporation (the “Company”), in connection with the preparation and filing of its Registration Statement on Form S-8 (the “Registration Statement”), which relates to the registration pursuant to the Securities Act of 1933, as amended (the “Act”), and the rules and regulations promulgated thereunder, of the offer and sale of a total of 10,000,000 shares of the common stock, $0.10 par value per share, of the Company (the “Common Stock”) pursuant to the Walmart 401(k) Plan, as amended (the “Plan”). The shares of Common Stock to which the Registration Statement relates are referred to herein as the “Shares.”

In rendering the opinion expressed herein, we have examined and relied upon, without investigation or independent verification, among other things, executed originals, counterparts or copies of the Restated Certificate of Incorporation and the Amended and Restated Bylaws of the Company, each as amended and restated to date, the Registration Statement in the form to be filed with the Securities and Exchange Commission (the “Commission”), the Plan, certain resolutions of the Board of Directors of the Company certified to us to be true and correct by the Company and other records and documents as we considered necessary or appropriate to enable us to express the opinion expressed herein. In all such examinations, we have assumed the authenticity and completeness of all documents submitted to us as originals and the conformity to authentic and complete originals of all documents submitted to us as photostatic, conformed, notarized or certified copies. As to facts material to our opinion, we have relied, to the extent that we deem such reliance proper and without investigation or independent verification, upon certificates of public officials and certificates of the Company or of officers or other representatives of the Company. For purposes of rendering the opinion expressed below, we have assumed (i) that any conditions to the issuance and sale of the Shares pursuant to the Plan made thereunder have been or will be satisfied in full at the time of each issuance of Shares pursuant to the Plan and (ii) that, at the time of issuance and sale of each of the Shares pursuant thereto, the Plan will remain in effect and will not have been amended or modified in any manner that affects adversely the validity of the Shares upon issuance under the terms of the Plan.

Based on the foregoing and subject to the assumptions, limitations and qualifications set forth herein, we are of the opinion that, subject to the Registration Statement becoming effective under the Act and compliance with all other applicable securities laws, the Shares issued after the date on which the Registration Statement becomes effective that are original issuance securities, when issued in accordance with the terms of the Plan upon receipt by the Company of payment for such Shares of an amount of cash, or other legal consideration having a value, of not less than the aggregate par value of such Shares and otherwise as provided for in the Plan and duly registered on the Company’s stock transfer records in the name or on behalf of the persons acquiring such Shares pursuant to the Plan, will be validly issued, fully paid and nonassessable.

The opinion expressed above is limited to the General Corporation Law of the State of Delaware and the applicable federal laws of the United States of America. The opinion expressed above is rendered as of the date hereof, and we assume no obligation to update or supplement such opinion to reflect any change of fact, circumstance or law after the date hereof. We express no legal opinion upon any matter other than that explicitly addressed above, and our express opinion herein contained shall not be interpreted to be an implied opinion upon any other matter.

Letter to Wal-Mart Stores, Inc.

March 27, 2013

Page 2

We hereby consent to the filing of this opinion as an exhibit to the Registration Statement. In giving this consent, we do not admit that we are included in the category of persons whose consent is required under Section 7 of the Act or the rules and regulations of the Commission promulgated thereunder.

Very truly yours,

/s/ Andrews Kurth LLP

- 2 -