MODIFICATION AGREEMENT (Long Form)

Exhibit 10.4

MODIFICATION AGREEMENT

(Long Form)

This Modification Agreement (“Agreement”) is made as of April 7, 2006 by Cost Plus, Inc., a California corporation (“Borrower”), and Bank of America, National Association, a national banking association (“Bank”).

Factual Background

A. Under a loan agreement dated May 14, 2004 (the “Loan Agreement”), Bank agreed to make a loan (the “Loan”) to Borrower. Capitalized terms used herein without definition have the meanings ascribed to them in the Loan Agreement.

B. The Loan is evidenced by (a) a Commercial Real Estate Loan Note dated May 14, 2004, made payable to Bank in the stated principal amount of $20,000,000.00 (the “Term Note”) and (b) a Revolving Loan Note dated May 14, 2004, made payable to Bank in the stated principal amount of $20,000,000.00 (the “Revolving Note”). The Term Note and the Revolving Note are referred to individually as a “Note” and collectively as “Notes”. The Notes are secured by a Deed of Trust dated May 14, 2004, executed by Borrower, as trustor, to PRLAP, Inc. as trustee, for the benefit of Bank as beneficiary. The Deed of Trust was recorded on May 14, 2004 in the Clerk’s Office of the Circuit Court of Isle of Wight County, Virginia as Instrument No. 04000005663. The Deed of Trust encumbers certain Property located in Isle of Wight County, Virginia, as more particularly therein described.

C. In connection with the Loan, Borrower executed an Environmental Indemnity Agreement (“Borrower’s Unsecured Indemnity”). Borrower’s Unsecured Indemnity is not a Loan Document, as defined below.

D. Cost Plus Management Services, Inc., a California corporation (“Management”), Cost Plus of Texas, a Texas corporation (“Texas”), and Cost Plus Marketing Services, Inc., a California corporation (“Marketing”) (each of Management, Texas and Marketing being a “Guarantor” and collectively, “Guarantors”) have guaranteed Borrower’s obligations to Bank, each in accordance with a Guaranty dated May 14, 2004.

E. Marketing has been merged into Management, with Management being the surviving corporation (“Guarantor Merger”).

F. Each of the Guarantors executed an Environmental Indemnity Agreement dated May 14, 2004 (an “Indemnity Agreement”), in connection with the Loan. In those Indemnity Agreements, the Guarantors, as indemnitors, agreed to indemnify Bank and certain other parties against certain environmental and other risks which may result from Bank’s having made the Loan.

G. As used herein, the term “Loan Documents” means the Loan Agreement, the Notes, the Deed of Trust, and any other documents executed in connection with the Loan, including those which evidence, guarantee, secure or modify the Loan, as any or all of them may have been amended to date. The Loan Documents, however, do not include Borrower’s Unsecured Indemnity or the Indemnity Agreements. This Agreement is a Loan Document.

1

H. As of the date of this Agreement, the outstanding principal balance of the Loan is $35,940,609.00 and no funds remain available to be advanced thereunder.

E. Borrower and Bank now wish to modify the Loan as set forth below.

Agreement

Therefore, Borrower and Bank agree as follows:

1. Modification of Loan Documents. The Loan Documents are hereby amended as follows:

(a) Borrower is entering into that certain Amendment to Credit Agreement dated as of April __, 2006, among Borrower, Bank as Administrative Agent, and the Lenders named therein (the “Amendment”). The Amendment modifies portions of the negative covenants set forth in Article VII of that certain Credit Agreement dated November 10, 2004, Bank among Borrower, as Administrative Agent and L/C Issuer, and the Lenders named therein (the “Credit Agreement”) with which Borrower is obligated to comply. Borrower acknowledges such modifications in the Amendment. Borrower further covenants to comply at all times with the negative covenants set forth in Article VII of the Credit Agreement as modified by the Amendment and as the Credit Agreement may be further amended, renewed, extended or replaced from time to time.

(b) The number “$7,500,000.00” in Section 6.15 of the Loan Agreement is deleted and replaced with “$15,000,000.00”.

(c) Section 6.16 of the Loan Agreement is amended and restated in full as follows:

“Unless the written consent of Lender is previously obtained, all or substantially all of the business assets of Borrower or any Guarantor are sold, Borrower or any Guarantor is dissolved, or there occurs any change in the form of business entity through which Borrower or any Guarantor presently conducts its business other than as permitted under Section 7.04 of the Credit Agreement.”

(d) The numbers “$5,000,000.00” and “$7,500,000.00” in Section 6.17 of the Loan Agreement are each deleted and replaced with “$15,000,000.00” in each instance.

(e) Section 8.17 of the Loan Agreement is amended and restated in full as follows:

8.17 Arbitration and Waiver of Jury Trial.

(a) This paragraph concerns the resolution of any controversies or claims between the parties, whether arising in contract, tort or by statute, including but not limited to controversies or claims that arise out of or relate to: (i) this agreement (including any renewals, extensions or modifications); or (ii) any document related to this agreement (collectively a “Claim”). For the purposes of this arbitration provision only, the term “parties” shall include any

2

parent corporation, subsidiary or affiliate of the Bank involved in the servicing, management or administration of any obligation described or evidenced by this agreement.

(b) At the request of any party to this agreement, any Claim shall be resolved by binding arbitration in accordance with the Federal Arbitration Act (Title 9, U.S. Code) (the “Act”). The Act will apply even though this agreement provides that it is governed by the law of a specified state. The arbitration will take place on an individual basis without resort to any form of class action.

(c) Arbitration proceedings will be determined in accordance with the Act, the then-current rules and procedures for the arbitration of financial services disputes of the American Arbitration Association or any successor thereof (“AAA”), and the terms of this paragraph. In the event of any inconsistency, the terms of this paragraph shall control. If AAA is unwilling or unable to (i) serve as the provider of arbitration or (ii) enforce any provision of this arbitration clause, any party to this agreement may substitute another arbitration organization with similar procedures to serve as the provider of arbitration.

(d) The arbitration shall be administered by AAA and conducted, unless otherwise required by law, in any U.S. state where real or tangible personal property collateral for this credit is located or if there is no such collateral, in the state specified in the governing law section of this agreement. All Claims shall be determined by one arbitrator; however, if Claims exceed Five Million Dollars ($5,000,000), upon the request of any party, the Claims shall be decided by three arbitrators. All arbitration hearings shall commence within ninety (90) days of the demand for arbitration and close within ninety (90) days of commencement and the award of the arbitrator(s) shall be issued within thirty (30) days of the close of the hearing. However, the arbitrator(s), upon a showing of good cause, may extend the commencement of the hearing for up to an additional sixty (60) days. The arbitrator(s) shall provide a concise written statement of reasons for the award. The arbitration award may be submitted to any court having jurisdiction to be confirmed, judgment entered and enforced.

(e) The arbitrator(s) will give effect to statutes of limitation in determining any Claim and may dismiss the arbitration on the basis that the Claim is barred. For purposes of the application of the statute of limitations, the service on AAA under applicable AAA rules of a notice of Claim is the equivalent of the filing of a lawsuit. Any dispute concerning this arbitration provision or whether a Claim is arbitrable shall be determined by the arbitrator(s). The arbitrator(s) shall have the power to award legal fees pursuant to the terms of this agreement.

(f) This paragraph does not limit the right of any party to: (i) exercise self-help remedies, such as but not limited to, setoff; (ii) initiate judicial or non-judicial foreclosure against any real or personal property collateral; (iii) exercise any judicial or power of sale rights, or (iv) act in a court of law to obtain an interim remedy, such as but not limited to, injunctive relief, writ of possession or appointment of a receiver, or additional or supplementary remedies.

(g) The procedure described above will not apply if the Claim, at the time of the proposed submission to arbitration, arises from or relates to an obligation to the Bank secured by real property. In this case, all of the parties to this agreement must consent to submission of the Claim to arbitration. If both parties do not consent to arbitration, the Claim will be resolved

3

as follows: The parties will designate a referee (or a panel of referees) selected under the auspices of AAA in the same manner as arbitrators are selected in AAA administered proceedings. The designated referee(s) will be appointed by a court as provided in California Code of Civil Procedure Section 638 and the following related sections. The referee (or presiding referee of the panel) will be an active attorney or a retired judge. The award that results from the decision of the referee(s) will be entered as a judgment in the court that appointed the referee, in accordance with the provisions of California Code of Civil Procedure Sections 644 and 645.

(h) The filing of a court action is not intended to constitute a waiver of the right of any party, including the suing party, thereafter to require submittal of the Claim to arbitration.

(i) By agreeing to binding arbitration, the parties irrevocably and voluntarily waive any right they may have to a trial by jury in respect of any Claim. Furthermore, without intending in any way to limit this agreement to arbitrate, to the extent any Claim is not arbitrated, the parties irrevocably and voluntarily waive any right they may have to a trial by jury in respect of such Claim. This provision is a material inducement for the parties entering into this agreement.

(f) The Guarantor Merger occurred without the prior written consent of Bank which is an Event of Default under Section 6.16 of the Loan Agreement. Bank hereby waives such Event of Default and any resulting cross default under Section 6.17 of the Loan Agreement caused by the Guarantor Merger (the “Waived Defaults”).

(g) Secured Obligations. The Deed of Trust is modified to secure payment and performance of the Loan as amended to date, in addition to all other “Secured Obligations” as therein defined. The foregoing notwithstanding, certain obligations continue to be excluded from the Secured Obligations, as provided in the Deed of Trust.

2. Conditions Precedent. Before this Agreement becomes effective and any party becomes obligated under it, all of the following conditions shall have been satisfied at Borrower’s sole cost and expense in a manner acceptable to Bank in the exercise of Bank’s sole judgment:

(a) Bank shall have received such assurance as Bank may require that the validity and priority of the Deed of Trust have not been and will not be impaired by this Agreement or the transactions contemplated by it.

(b) Bank shall have received fully executed and, where appropriate, acknowledged originals of this Agreement, the attached consents signed by each Guarantor and any other documents which Bank may require or request in accordance with this Agreement or the other Loan Documents.

(c) Bank shall have received reimbursement, in immediately available funds, of all costs and expenses incurred by Bank in connection with this Agreement, including legal fees and expenses of Bank’s counsel, including the market value of services of in-house counsel.

4

3. Borrower’s Representations and Warranties. Borrower represents and warrants to Bank as follows:

(a) Recitals. The recitals set forth above in the Factual Background are true, accurate and correct.

(b) Loan Documents. All representations and warranties made and given by Borrower in the Loan Documents and Borrower’s Unsecured Indemnity are true, accurate and correct.

(c) No Default. Other than the Waived Defaults, no Event of Default has occurred and is continuing, and no event has occurred and is continuing which, with notice or the passage of time or both, would be an Event of Default.

(d) Property. Borrower lawfully possesses and holds fee simple title to all of the Property which is real property, and the Deed of Trust is a first and prior lien on that property. Borrower owns all of the Property which is personal property free and clear of any reservations of title and conditional sales contracts, and also of any security interests other than the Deed of Trust, which is a first and prior lien on such property. There is no financing statement affecting the Property on file in California or Virginia except for financing statements in favor of Bank.

(e) Borrowing Entity. Borrower is a corporation having its chief executive office in the State of California. Borrower’s state of incorporation is California and Borrower is validly existing under the laws of that State. There have been no changes in the legal structure of Borrower since the inception of the Loan. Borrower’s exact legal name is set forth in the first paragraph of this Agreement.

(f) Financial Information. All financial information which has been and will be delivered to Bank, including all information relating to the financial condition of Borrower or any shareholders, guarantor or the Property, fairly and accurately represents the financial condition being reported on, including all material contingent liabilities. All such information was prepared in accordance with generally accepted accounting principles consistently applied, unless otherwise noted, and was in compliance with all government regulations that apply. Since the dates of the financial information specified above, there has been no material adverse change in the business condition (financial or otherwise), operations, properties or prospects of Borrower or any other subject thereof.

4. WAIVER OF JURY TRIAL. BORROWER AND BANK WAIVE TRIAL BY JURY IN RESPECT OF ANY “CLAIM” AS DEFINED IN SECTION 8.17 OF THE LOAN AGREEMENT. THIS WAIVER IS KNOWINGLY, WILLINGLY AND VOLUNTARILY MADE BY BORROWER AND BANK, AND BORROWER AND BANK HEREBY REPRESENT THAT NO REPRESENTATIONS OF FACT OR OPINION HAVE BEEN MADE BY ANY PERSON OR ENTITY TO INDUCE THIS WAIVER OF TRIAL BY JURY OR TO IN ANY WAY MODIFY OR NULLIFY ITS EFFECT. THIS PROVISION IS A MATERIAL INDUCEMENT FOR THE PARTIES ENTERING INTO THE LOAN MODIFICATION. BORROWER AND BANK ARE EACH HEREBY

5

AUTHORIZED TO FILE A COPY OF THIS SECTION 4 IN ANY PROCEEDING AS CONCLUSIVE EVIDENCE OF THIS WAIVER OF JURY TRIAL. BORROWER FURTHER REPRESENTS AND WARRANTS THAT IT HAS BEEN REPRESENTED IN THE SIGNING OF THIS AGREEMENT AND IN THE MAKING OF THIS WAIVER BY INDEPENDENT LEGAL COUNSEL, OR HAS HAD THE OPPORTUNITY TO BE REPRESENTED BY INDEPENDENT LEGAL COUNSEL SELECTED OF ITS OWN FREE WILL, AND THAT IT HAS HAD THE OPPORTUNITY TO DISCUSS THIS WAIVER WITH COUNSEL.

5. Incorporation. This Agreement shall form a part of each Loan Document, and all references to a given Loan Document shall mean that document as hereby modified.

6. No Prejudice; Reservation of Rights. This Agreement shall not prejudice any rights or remedies of Bank under the Loan Documents or Borrower’s Unsecured Indemnity. Bank reserves, without limitation, all rights which it has against any indemnitor, guarantor, or endorser of the Note.

7. Reaffirmation; No Impairment; No Novation. Borrower hereby reaffirms all of its obligations under the Loan Documents and Borrower’s Unsecured Indemnity. Except as specifically hereby amended, the Loan Documents and Borrower’s Unsecured Indemnity shall each remain unaffected by this Agreement and all such documents shall remain in full force and effect. Nothing in this Agreement shall impair the lien of the Deed of Trust, which as hereby amended shall remain one deed of trust with one power of sale, creating a first lien encumbering the Property. The execution and delivery of this Agreement shall not constitute a novation of the Loan.

8. Purpose and Effect of Bank’s Approval. Bank’s approval of any matter in connection with the Loan shall be for the sole purpose of protecting Bank’s security and rights. No such approval shall result in a waiver of any default of Borrower other than the Waived Defaults. In no event shall Bank’s approval be a representation of any kind with regard to the matter being approved.

9. Disclosure to Title Company. Without notice to or the consent of Borrower, Bank may disclose to any title insurance company which insures any interest of Bank under the Deed of Trust (whether as primary insurer, coinsurer or reinsurer) any information, data or material in Bank’s possession relating to Borrower, the Loan, the Improvements or the Property.

10. Further Assurances. Borrower agrees that immediately upon Bank’s demand, Borrower shall execute and deliver to Bank, and shall cause any necessary third parties to execute and deliver to Bank, all documents and filings (including “account control agreements”), and shall otherwise take all other actions that may be requested by Bank in order to maintain and provide to Bank a first-priority perfected security interest in all collateral, and Borrower hereby agrees to pay all fees and costs associated therewith, including the reasonable fees and costs of Bank’s inside and outside counsel.

11. Integration. The Loan Documents, including this Agreement, and Borrower’s Unsecured Indemnity: (a) integrate all the terms and conditions mentioned in or incidental to the

6

Loan Documents and Borrower’s Unsecured Indemnity; (b) supersede all oral negotiations and prior and other writings with respect to their subject matter; and (c) are intended by the parties as the final expression of the agreement with respect to the terms and conditions set forth in those documents and as the complete and exclusive statement of the terms agreed to by the parties. If there is any conflict between the terms, conditions and provisions of this Agreement and those of any other agreement or instrument, including any of the other Loan Documents or Borrower’s Unsecured Indemnity, the terms, conditions and provisions of this Agreement shall prevail.

12. Miscellaneous. This Agreement and any attached consents or exhibits requiring signatures may be executed in counterparts, and all counterparts shall constitute but one and the same document. If any court of competent jurisdiction determines any provision of this Agreement or any of the other Loan Documents or Borrower’s Unsecured Indemnity to be invalid, illegal or unenforceable, that portion shall be deemed severed from the rest, which shall remain in full force and effect as though the invalid, illegal or unenforceable portion had never been a part of the Loan Documents or Borrower’s Unsecured Indemnity. This Agreement shall be governed by the laws of the State of California, without regard to the choice of law rules of that State. As used herein, the word “include(s)” means “includes(s), without limitation,” and the word “including” means “including, but not limited to.”

7

GUARANTORS’ CONSENT

1. Cost Plus Management Services, Inc., a California corporation and successor by merger to Cost Plus Marketing Services, Inc., a California corporation, and Cost Plus of Texas, Inc., a Texas corporation (each a “Guarantor”) each hereby consents to the terms, conditions and provisions of the foregoing Modification Agreement and the transactions contemplated by that agreement. Each Guarantor hereby reaffirms the full force and effectiveness of its Guaranty Agreement dated May 14, 2004, (“Guaranty”) and each Guarantor reaffirms the full force and effectiveness of its Environmental Indemnity Agreement dated May 14, 2004 (“Indemnity”). In addition, each Guarantor acknowledges that its obligations under the Guaranty and Indemnity are separate and distinct from those of Borrower on the Loan.

2. Each Guarantor agrees that Section 21 of its Guaranty is amended and restated as follows:

21. Arbitration and Waiver of Jury Trial.

(a) This paragraph concerns the resolution of any controversies or claims between the parties, whether arising in contract, tort or by statute, including but not limited to controversies or claims that arise out of or relate to: (i) this agreement (including any renewals, extensions or modifications); or (ii) any document related to this agreement (collectively a “Claim”). For the purposes of this arbitration provision only, the term “parties” shall include any parent corporation, subsidiary or affiliate of the Bank involved in the servicing, management or administration of any obligation described or evidenced by this agreement.

(b) At the request of any party to this agreement, any Claim shall be resolved by binding arbitration in accordance with the Federal Arbitration Act (Title 9, U.S. Code) (the “Act”). The Act will apply even though this agreement provides that it is governed by the law of a specified state. The arbitration will take place on an individual basis without resort to any form of class action.

(c) Arbitration proceedings will be determined in accordance with the Act, the then-current rules and procedures for the arbitration of financial services disputes of the American Arbitration Association or any successor thereof (“AAA”), and the terms of this paragraph. In the event of any inconsistency, the terms of this paragraph shall control. If AAA is unwilling or unable to (i) serve as the provider of arbitration or (ii) enforce any provision of this arbitration clause, any party to this agreement may substitute another arbitration organization with similar procedures to serve as the provider of arbitration.

(d) The arbitration shall be administered by AAA and conducted, unless otherwise required by law, in any U.S. state where real or tangible personal property collateral for this credit is located or if there is no such collateral, in the state specified in the governing law section of this agreement. All Claims shall be determined by one arbitrator; however, if Claims exceed Five Million Dollars ($5,000,000), upon the request of any party, the Claims shall be decided by three arbitrators. All arbitration hearings shall commence within ninety (90) days of the demand for arbitration and close within ninety (90) days of commencement and the award of the arbitrator(s) shall be issued within thirty (30) days of the close of the hearing. However,

1

the arbitrator(s), upon a showing of good cause, may extend the commencement of the hearing for up to an additional sixty (60) days. The arbitrator(s) shall provide a concise written statement of reasons for the award. The arbitration award may be submitted to any court having jurisdiction to be confirmed, judgment entered and enforced.

(e) The arbitrator(s) will give effect to statutes of limitation in determining any Claim and may dismiss the arbitration on the basis that the Claim is barred. For purposes of the application of the statute of limitations, the service on AAA under applicable AAA rules of a notice of Claim is the equivalent of the filing of a lawsuit. Any dispute concerning this arbitration provision or whether a Claim is arbitrable shall be determined by the arbitrator(s). The arbitrator(s) shall have the power to award legal fees pursuant to the terms of this agreement.

(f) This paragraph does not limit the right of any party to: (i) exercise self-help remedies, such as but not limited to, setoff; (ii) initiate judicial or non-judicial foreclosure against any real or personal property collateral; (iii) exercise any judicial or power of sale rights, or (iv) act in a court of law to obtain an interim remedy, such as but not limited to, injunctive relief, writ of possession or appointment of a receiver, or additional or supplementary remedies.

(g) The procedure described above will not apply if the Claim, at the time of the proposed submission to arbitration, arises from or relates to an obligation to the Bank secured by real property. In this case, all of the parties to this agreement must consent to submission of the Claim to arbitration. If both parties do not consent to arbitration, the Claim will be resolved as follows: The parties will designate a referee (or a panel of referees) selected under the auspices of AAA in the same manner as arbitrators are selected in AAA administered proceedings. The designated referee(s) will be appointed by a court as provided in California Code of Civil Procedure Section 638 and the following related sections. The referee (or presiding referee of the panel) will be an active attorney or a retired judge. The award that results from the decision of the referee(s) will be entered as a judgment in the court that appointed the referee, in accordance with the provisions of California Code of Civil Procedure Sections 644 and 645.

(h) The filing of a court action is not intended to constitute a waiver of the right of any party, including the suing party, thereafter to require submittal of the Claim to arbitration.

(i) By agreeing to binding arbitration, the parties irrevocably and voluntarily waive any right they may have to a trial by jury in respect of any Claim. Furthermore, without intending in any way to limit this agreement to arbitrate, to the extent any Claim is not arbitrated, the parties irrevocably and voluntarily waive any right they may have to a trial by jury in respect of such Claim. This provision is a material inducement for the parties entering into this agreement.

2

3