Exhibit 5.1

[Letterhead of Andrews Kurth LLP]

July 28, 2010

Wal-Mart Stores, Inc.

702 Southwest Eighth Street

Bentonville, Arkansas 72716

Re: Wal-Mart Stores, Inc.

Registration Statement on Form S-8 relating to the ASDA Sharesave Plan 2000

Ladies and Gentlemen:

We have acted as special counsel for Wal-Mart Stores, Inc., a Delaware corporation (the “Company”), in connection with its registration of 15,000,000 shares of the common stock, $0.10 par value per share, of the Company (the “Shares”) that may be issued by the Company pursuant to the ASDA Sharesave Plan 2000 as amended and in effect on the date hereof and as it may hereafter be amended or amended and restated (the “Plan”) and awards of rights to acquire Shares made to employees of ASDA Group Limited, a wholly-owned subsidiary of the Company, pursuant to the Plan (“Awards”). The issuance of the Shares will be registered by means of the Company’s Registration Statement on Form S-8 filed with the Securities and Exchange Commission under the Securities Act of 1933, as amended (“Registration Statement”).

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, certain resolutions of the Executive Committee of the Board of Directors of the Company certified to us to be true and correct by the Company, the Plan 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 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 of the Shares pursuant to the Plan and the Awards 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 the Plan will remain in effect at the time of issuance of each of the Shares pursuant thereto 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, and none of the Awards and the agreements, documents and instruments governing the award, offer and sale of the Shares pursuant to the Plan (collectively, the “Award Documents”) will contain any provision, inconsistent with such opinion.

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 Securities Act of 1933, as amended, and compliance with all other applicable securities laws, the Shares that are original issuance securities, when issued in accordance with the terms of the Plan and the terms of the applicable Award Documents 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 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 and applicable Award Documents, will be validly issued, fully paid and nonassessable.

The opinion expressed above is limited to the General Corporation Law of the State of Delaware (including applicable provisions of the Constitution of the State of Delaware and reported judicial decisions interpreting those laws) 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.

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 Securities Act of 1933, as amended, or the rules and regulations of the Commission promulgated thereunder.

Very truly yours,

/s/ Andrews Kurth LLP