Exhibit 5.1

Letterhead of Andrews Kurth LLP

September 9, 2005

Wal-Mart Stores, Inc.

702 S.W. Eighth Street

Bentonville, Arkansas 72716

Re: Wal-Mart Stores, Inc.

Registration Statement on Form S-8 regarding Wal-Mart Stores, Inc. Stock Incentive Plan of 2005

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 50,000,000 shares of the common stock, $.10 par value per share, of the Company (the “Shares”) that may issued by the Company pursuant to the Wal-Mart Stores, Inc. Stock Incentive Plan of 2005 (the “Plan”). 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 By-laws 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, 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.

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 applicable state securities laws, the Shares, when issued in accordance with the terms of the Plan and the terms of the agreements and other instruments governing the award, offer and sale of the Shares under the Plan, will be validly issued, fully paid and nonassessable.

The opinion expressed above is limited to the effect of the Constitution of the State of Delaware, the Delaware General Corporation Law and the reported judicial decisions of the courts of the State of Delaware interpreting the pertinent provisions of the Constitution of the State of Delaware and the Delaware General Corporation Law and the applicable federal laws of the United States. 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 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