SECOND AMENDMENT TO CREDIT AGREEMENT AND WAIVER

Exhibit 10.4

SECOND AMENDMENT TO CREDIT AGREEMENT AND WAIVER

This SECOND AMENDMENT TO CREDIT AGREEMENT AND WAIVER (this “Amendment”), dated as of April 20, 2004, is entered into by and among COST PLUS, INC., a California corporation (the “Borrower”), each lender from time to time party to the Credit Agreement referred to below (each, a “Lender,” and collectively, the “Lenders”) and BANK OF AMERICA, N.A., as Administrative Agent (in such capacity, the “Administrative Agent”) and L/C Issuer.

RECITALS

A. The Borrower, the Lenders, and the Administrative Agent are parties to a Credit Agreement dated as of May 30, 2002, as amended by that Amendment to Credit Agreement dated as of February 12, 2003 (as so and further amended, restated, extended, supplemented or otherwise modified from time to time, the “Credit Agreement”), pursuant to which the Administrative Agent and the Lenders have extended certain credit facilities to the Borrower.

B. At the time of the execution of the Credit Agreement, certain capital leases were inadvertently characterized as operating leases and therefore not correctly scheduled under the Credit Agreement.

C. With respect to one of the capital leases referred to in Recital B, the Borrower is currently contemplating acquiring the real property that is the subject of such capital lease.

D. The Borrower has requested that the Administrative Agent and the Lenders agree to certain amendments to the Credit Agreement to (i) correctly reflect the capital leases referred to in Recital B and to provide certain waivers in connection with the prior inadvertent classification as operating leases under the Credit Agreement, and (ii) permit the Borrower to acquire the real property referred to in Recital C, and the Lenders have agreed to such request, subject to the terms and conditions of this Amendment.

NOW, THEREFORE, for valuable consideration, the receipt and adequacy of which are hereby acknowledged, the parties hereto hereby agree as follows:

1. Defined Terms. Unless otherwise defined herein, capitalized terms used herein shall have the meanings, if any, assigned to such terms in the Credit Agreement.

2. Interpretation. The rules of interpretation set forth in Sections 1.02, 1.03, 1.04, 1.05, 1.06 and 1.07 of the Credit Agreement shall be applicable to this Amendment and are incorporated herein by this reference, except that any reference in this Amendment to a section is, unless otherwise stated, a reference to a section of the Credit Agreement.

3. Amendment of Credit Agreement. Subject to the terms and conditions hereof, effective as of the Effective Date, the Credit Agreement shall be amended as follows:

(a) Section 1.01 shall be amended by inserting the following definition in alphabetical order:

“Existing Windsor Facility” means the Borrower’s distribution facility and related assets commonly known as Building 1 in Windsor, Virginia.

“Existing Windsor Facility Lease” means that certain Lease Agreement relating to the Existing Windsor Facility entered into by and between the Borrower and G.E.M. Big Bethel LLC dated as of November 1, 2001, as amended.

“New Windsor Facility” means the distribution facility and related assets to be constructed and completed on or before November 15, 2005 in Windsor, Virginia, adjacent to the Existing Windsor Facility.

(b) Section 7.01(a) shall be amended by (i) deleting the word “and” from the end of subsection (xii) thereof, (ii) deleting the period at the end of subsection (xiii) thereof and replacing it with “;”, and (iii) adding the following new subsections (xiv), (xv) and (xvi) immediately after subsection (xiii):

“(xiv) Liens on the Existing Windsor Facility securing Indebtedness permitted by Section 7.03 (i), (j) or (k);

(xv) Liens on the Existing Windsor Facility and the New Windsor Facility securing Indebtedness permitted by Section 7.03(d), to the extent such Indebtedness is incurred in order to hedge interest rate risk relating to Indebtedness permitted by Section 7.03(i), (j) or (k); and

(xvi) Liens on the New Windsor Facility securing Indebtedness permitted by Section 7.03(j) or (k).”

(c) Section 7.03(f) shall be amended and replaced in its entirety with the following:

“(f) Indebtedness in respect of capital leases, Synthetic Lease Obligations and purchase money obligations for PP&E; provided, however, that the aggregate amount of all such Indebtedness at any one time outstanding (excluding any capital leases, Synthetic Lease Obligations and purchase money obligations for PP&E set forth in Schedule 7.03 (and for which the Lien relating to each shall be deemed a Permitted Lien under Section 7.01(a)(ix) without regard to Section 7.11)) shall not exceed the amount set forth in Section 7.11;”

(d) Section 7.03 shall be further amended by (i) deleting the word “and” from the end of subsection (g) thereof, (ii) deleting the period at the end of subsection (h) thereof and replacing it with “;”, and (iii) adding the following new subsections (i), (j) and (k) immediately after subsection (h):

“(i) Indebtedness consisting of the Existing Windsor Facility Lease and refinancings, refundings, renewals or extensions thereof, provided that the amount

of such Indebtedness is not thereby increased except by an amount equal to a reasonable premium paid, and fees and expenses reasonably incurred, in connection with such refinancing, and provided further that the aggregate amount of all such Indebtedness at any time outstanding shall not exceed $20,000,000;

(j) Indebtedness consisting of loans incurred in connection with the acquisition of the Existing Windsor Facility, including any financed amounts relating to the termination of the Existing Windsor Facility Lease, together with any refinancings, refundings, renewals or extensions thereof, provided that the amount of such Indebtedness is not thereby increased except by an amount equal to a reasonable premium paid, and fees and expenses reasonably incurred, in connection with such refinancing, and provided further that the aggregate amount of all such Indebtedness at any time outstanding shall not exceed $20,000,000; and

(k) Indebtedness consisting of loans incurred in connection with the acquisition and construction of the New Windsor Facility, and any refinancings, refundings, renewals or extensions thereof, provided that the amount of such Indebtedness is not thereby increased except by an amount equal to a reasonable premium paid, and fees and expenses reasonably incurred, in connection with such refinancing, and provided further that the aggregate principal amount of all such Indebtedness at any time outstanding shall not exceed $20,000,000.”

(e) Schedule 7.03 to the Disclosure Letter is deleted and replaced in its entirety with Schedule 7.03 attached hereto.

(f) Section 7.11 shall be amended by deleting the table contained therein and replacing it with the following:

4. Waiver.

(a) Waived Defaults. For purposes of this Amendment, “Waived Defaults” shall mean:

(i) Any Default or Event of Default existing as of the Effective Date under Section 8.01(d) solely as a consequence of a breach by the Borrower of the representations and warranties contained in Section 5.07 by virtue of the Waived Defaults described in clauses (ii), (iii), (iv), (v) and (vi) of this Section 4(a).

(ii) Any Default or Event of Default existing as of the Effective Date under Section 8.01(d) solely as a consequence of a breach by the Borrower of the representations and warranties contained in Section 5.08 by virtue of the existence of the Liens described in Section 7.01(a)(xiv).

(iii) Any Default or Event of Default existing as of the Effective Date under Section 8.01(b) solely as a consequence of the existence of the Liens on the Existing Windsor Facility described in Section 7.01(a)(xiv).

(iv) Any Default or Event of Default existing as of the Effective Date under Section 8.01(b) solely as a consequence of the existence of the Indebtedness described in Section 7.03(i).

(v) Any Default or Event of Default existing as of the Effective Date under Section 8.01(b) solely as a consequence of the existence of any Indebtedness not set forth on Schedule 7.03 prior to the Effective Date and not permitted by Section 7.11.

(vi) Any Default or Event of Default existing as of the Effective Date under Section 8.01(b) solely as a consequence of the existence of one or more Liens relating to capital leases not set forth on Schedule 7.03 prior to the Effective Date and not permitted by Section 7.11.

(b) Subject to and upon the terms and conditions hereof, the Lenders hereby waive the Waived Defaults upon the Effective Date.

(c) Nothing contained herein shall be deemed a waiver of (or otherwise affect the Administrative Agent’s or the Lenders’ ability to enforce) any other Default or Event of Default, including without limitation (i) any Default or Event of Default as may now or hereafter exist and arise from or otherwise be related to the Waived Defaults (including without limitation any cross-default arising under the Credit Agreement by virtue of any matters resulting from the Waived Defaults), and (ii) any Default or Event of Default arising at any time after the Effective Date and which is similar in type to any of the Waived Defaults.

5. Representations and Warranties. The Borrower hereby represents and warrants to the Administrative Agent and the Lenders as follows:

(a) Other than the Waived Defaults, no Default or Event of Default has occurred and is continuing.

(b) The execution, delivery and performance by the Borrower of this Amendment have been duly authorized by all necessary corporate and other action and do not and will not require any registration with, consent or approval of, or notice to or action by, any Person (including any Governmental Authority) in order to be effective and enforceable.

(c) This Amendment constitutes the legal, valid and binding obligations of the Borrower, enforceable against it in accordance with their respective terms, without defense, counterclaim or offset.

(d) Subject to the Waived Defaults, all representations and warranties of the Borrower contained in Article V are true and correct on and as of the Effective Date, except to the extent that any such representation and warranty specifically relates to an earlier date.

(e) The Borrower is entering into this Amendment on the basis of its own investigation and for its own reasons, without reliance upon the Administrative Agent and the Lenders or any other Person.

6. Effective Date.

(a) This Amendment will become effective when each of the following conditions precedent has been satisfied (the “Effective Date”):

(i) The Administrative Agent shall have received from the Borrower and the Required Lenders a duly executed original (or, if elected by the Administrative Agent, an executed facsimile copy) counterpart to this Amendment.

(ii) The Administrative Agent shall have received from the Borrower a certificate signed by the secretary or assistant secretary of the Borrower dated the Effective Date, in form and substance satisfactory to the Administrative Agent, certifying evidence of the authorization of the execution, delivery and performance by the Borrower of this Amendment.

(iii) The Administrative Agent shall have received from the Borrower a certificate signed by a Responsible Officer of the Borrower dated the Effective Date, in form and substance satisfactory to the Administrative Agent, certifying that all representations and warranties contained herein are true and correct on and as of the Effective Date, as though made on such date.

(iv) The Administrative Agent shall have received, in form and substance satisfactory to it, such additional approvals, consents, opinions, documents and other information as the Administrative Agent shall request.

(b) For purposes of determining compliance with the conditions specified in this Section 6, each Lender that has executed this Amendment and delivered it to the Administrative Agent shall be deemed to have consented to, approved or accepted, or to be satisfied with, each document or other matter either sent, or made available for inspection, by the Administrative Agent to such Lender for consent, approval, acceptance or satisfaction, or required thereunder to be consented to or approved by or acceptable or satisfactory to such Lender.

(c) From and after the Effective Date, the Credit Agreement is amended as set forth herein. Except as expressly amended pursuant hereto, the Credit Agreement shall remain unchanged and in full force and effect and is hereby ratified and confirmed in all respects.

(d) The Administrative Agent will notify the Borrower and the Lenders of the occurrence of the Effective Date.

7. Reservation of Rights. The Borrower acknowledges and agrees that neither the execution on delivery by the Administrative Agent and the Lenders of this Amendment, shall be deemed to create a course of dealing or otherwise obligate the Administrative Agent or the Lenders to execute similar amendments under the same or similar circumstances in the future.

8. Miscellaneous.

(a) This Amendment shall be binding upon and inure to the benefit of the parties hereto and thereto and their respective successors and assigns. No third party beneficiaries are intended in connection with this Amendment.

(b) THIS AMENDMENT IS SUBJECT TO THE PROVISIONS OF SECTIONS 10.17 AND 10.18 OF THE CREDIT AGREEMENT RELATING TO GOVERNING LAW, VENUE AND WAIVER OF RIGHT TO TRIAL BY JURY, THE PROVISIONS OF WHICH ARE BY THIS REFERENCE INCORPORATED HEREIN IN FULL.

(c) This Amendment may be executed in any number of counterparts, each of which shall be deemed an original, but all such counterparts together shall constitute but one and the same instrument. Transmission of signatures of any party by facsimile shall for all purposes be deemed the delivery of original, executed counterparts thereof and the Administrative Agent is hereby authorized to make sufficient photocopies thereof to assemble complete counterparty documents.

(d) This Amendment, together with the Credit Agreement, contains the entire and exclusive agreement of the parties hereto with reference to the matters discussed herein and therein. This Amendment supersedes all prior drafts and communications with respect thereto. This Amendment may not be amended except in accordance with the provisions of Section 10.01 of the Credit Agreement.

(e) If any term or provision of this Amendment shall be deemed prohibited by or invalid under any applicable law, such provision shall be invalidated without affecting the remaining provisions of this Amendment or the Credit Agreement, respectively.

(f) The Borrower covenants to pay to or reimburse the Administrative Agent, upon demand, for all costs and expenses (including allocated costs of in-house counsel) incurred in connection with the development, preparation, negotiation, execution and delivery of this Amendment.

(g) This Amendment shall constitute a “Loan Document” under and as defined in the Credit Agreement.

IN WITNESS WHEREOF, the parties hereto have caused this Amendment to be duly executed as of the date first above written.

Signature Page 1 to Second Amendment to Credit Agreement and Waiver

Signature Page 2 to Second Amendment to Credit Agreement and Waiver

Signature Page 3 to Second Amendment to Credit Agreement and Waiver

Signature Page 4 to Second Amendment to Credit Agreement and Waiver

EXISTING INDEBTEDNESS (Schedule 7.03)

Indebtedness under leases disclosed under Schedule 7.01.

Indebtedness related to the following non-equipment capital leases:

Schedule 7.03