Exhibit 5.1

[PERKINS COIE LETTERHEAD]

December 3, 2012

Costco Wholesale Corporation

999 Lake Drive

Issaquah, Washington 98027

Ladies and Gentlemen:

We have acted as counsel to Costco Wholesale Corporation, a Washington corporation (the “Company”), in connection with the preparation and filing with the Securities and Exchange Commission (the “Commission”) pursuant to the Securities Act of 1933, as amended (the “Securities Act”), and the rules and regulations promulgated thereunder (the “Rules”), of a registration statement on Form S-3 (Registration No. 333-185166), filed November 28, 2012 (the “Registration Statement”), including the prospectus constituting a part thereof, dated November 28, 2012 (the “Base Prospectus”), the preliminary prospectus supplement to the Base Prospectus, dated November 28, 2012 and the prospectus supplement to the Base Prospectus, dated November 28, 2012 (the “Prospectus Supplement” and, together with the Base Prospectus, the “Prospectus”) relating to the issuance and sale by the Company pursuant to the Underwriting Agreement (as defined below) of $1.2 billion aggregate principal amount of the Company’s 0.650% Senior Notes due December 7, 2015, $1.1 billion aggregate principal amount of the Company’s 1.125% Senior Notes due December 15, 2017, and $1.2 billion aggregate principal amount of the Company’s 1.700% Senior Notes due December 15, 2019 (collectively, the “Debt Securities”).

The Debt Securities are to be issued pursuant to a First Supplemental Indenture dated as of March 20, 2002 (the “First Supplemental Indenture”), between the Company and U.S. Bank National Association (the “Debt Trustee”), as trustee, to the Senior Debt Securities Indenture dated as of October 26, 2001 (together with the First Supplemental Indenture, the “Indenture”). The Indenture has been incorporated by reference as an exhibit into the Registration Statement.

In our capacity as counsel to the Company, we have examined or are otherwise familiar with (a) the Company’s Amended and Restated Articles of Incorporation, (b) the Company’s Bylaws, (c) the Registration Statement (including the Prospectus), (d) the Indenture, (e) the Underwriting Agreement dated November 28, 2012 between the Company and J.P. Morgan Securities LLC and Merrill Lynch, Pierce, Fenner & Smith Incorporated, as representatives of the underwriters named therein (the “Underwriting Agreement”), (f) the form of each of the Debt Securities, (g) such of the corporate proceedings with respect to the issuance and sale of the Debt Securities as have occurred prior to or as of the date hereof, and (h) such other documents, records and instruments as we have deemed necessary for the purposes of this opinion.

As to matters of fact material to the opinions expressed herein, we have relied on (a) information in public authority documents (and all opinions based on public authority documents are as of the date of such public authority documents and not as of the date of this opinion letter), and (b) information provided in certificates of officers of the Company. We have not independently verified the facts so relied on.

In such examination, we have assumed the following without investigation: (i) the authenticity of original documents and the genuineness of all signatures; (ii) the conformity to the originals of all documents submitted to us as copies; (iii) the truth, accuracy and completeness of the information, representations and warranties contained in the records, documents, instruments and certificates we have reviewed (collectively, the “Documents”); (iv) with respect to each party to the Documents other than the Company, the requisite power and due authorization, corporate or otherwise, of such party to enter into the Documents and to perform all obligations thereunder, (v) with respect to each party to the Documents other than the Company, the validity and binding effect of the Documents and enforceability of the Documents, in accordance with their terms, against such party.

Based on and subject to the foregoing, we are of the opinion that the Debt Securities have been duly authorized by the Company for offer, sale, issuance and delivery, and, when duly executed by the Company and authenticated by the Debt Trustee in accordance with the Indenture and delivered to and paid for by the purchasers thereof as contemplated by the Underwriting Agreement and the Prospectus, such Debt Securities will constitute valid and legally binding obligations of the Company, enforceable against the Company in accordance with the terms thereof.

The foregoing opinions are subject to the following exclusions and qualifications:

-2-

We hereby consent to the filing of this opinion as Exhibit 5.1 to the Company’s Current Report on Form 8-K filed with the Commission on or about the date hereof, to the incorporation by reference of this opinion into the Registration Statement and the Prospectus, and to the reference to our firm in the Prospectus under the heading “Legal Matters.” 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 or related Rules.

-3-