AMENDMENT NO. 1 TO THE AMENDED AND RESTATED PREFERRED SHARES RIGHTS AGREEMENT

Exhibit 4.1

AMENDMENT NO. 1 TO THE AMENDED AND RESTATED PREFERRED SHARES

RIGHTS AGREEMENT

This Amendment to the Amended and Restated Preferred Shares Rights Agreement dated as of June 24, 2008 (the “Restated Rights Agreement”), between Cost Plus, Inc., a California corporation (the “Company”), and Computershare Trust Company, N.A., as the rights agent, is dated as of January 7, 2009 (this “Amendment”).

WHEREAS, pursuant to Section 27 of the Agreement, the Board of Directors of the Company has determined that it is in the best interests of the Company and its shareholders to amend the terms of the Agreement in certain respects.

NOW, THEREFORE, in consideration of the promises and the mutual agreements herein set forth, and intending to be legally bound hereby, the parties hereto agree that the Restated Rights Agreement shall be and hereby is amended in the following manner. Capitalized terms that are not otherwise defined herein shall have the meanings ascribed to them in the Restated Rights Agreement.

Section 1. Amendment of “Certain Definitions” Section.

(a) Section 1(a) of the Agreement is hereby amended and restated in its entirety to read as follows:

“(a) “Acquiring Person” shall mean any Person who or which, together with all Affiliates and Associates of such Person, shall be the Beneficial Owner of fifteen percent (15%) or more of the Common Shares then outstanding, but shall not include the Company, any Subsidiary of the Company or any employee benefit plan of the Company or of any Subsidiary of the Company, or any entity holding Common Shares for or pursuant to the terms of any such plan; provided, however, that any Person who shall have executed a written agreement with the Company, which agreement shall have been approved by the Board prior to the date on which such Person, together with all Affiliates and Associates, became the Beneficial Owner of fifteen percent (15%) or more of the Common Shares then outstanding, and which agreement imposes certain limitations as determined by the Board on such Person, but only if and so long as (A) such Person is not the Beneficial Owner of more than 19.9% of the Common Shares outstanding, (B) such agreement continues to be binding on such Person, (C) such Person is in substantial compliance (as determined by the Board in its discretion) with the terms of such agreement, as amended from time to time, (D) any and all amendments to such agreement have been approved by the Board, and (E) no amendments, if executed after the Distribution Date, cure, or have the effect of curing, any prior breach of such agreement or any amendment thereto, shall not be deemed an “Acquiring Person” (any such exempted Person, an “Exempt Person”) until such time as such Exempt Person shall be the Beneficial Owner of twenty percent (20%) or more of the Common Shares then outstanding. Notwithstanding the foregoing, no Person shall be deemed to be an Acquiring Person as the result of an acquisition of Common Shares by the Company which,

by reducing the number of shares outstanding, increases the proportionate number of shares beneficially owned by such Person to fifteen percent (15%) or more of the Common Shares of the Company then outstanding (or with respect to an Exempt Person, increases such number of shares to twenty percent (20%) or more of the Common Shares of the Company then outstanding); provided, however, that if a Person shall become the Beneficial Owner of fifteen percent (15%) or more of the Common Shares of the Company then outstanding (or with respect to an Exempt Person, shall become the Beneficial Owner of twenty percent (20%) or more of the Common Shares of the Company then outstanding) by reason of share purchases by the Company and shall, after such share purchases by the Company, become the Beneficial Owner of any additional Common Shares of the Company (other than pursuant to a dividend or distribution paid or made by the Company on the outstanding Common Shares in Common Shares or pursuant to a split or subdivision of the outstanding Common Shares), then such Person shall be deemed to be an Acquiring Person unless upon becoming the Beneficial Owner of such additional Common Shares of the Company such Person does not beneficially own fifteen percent (15%) or more of the Common Shares of the Company then outstanding (or with respect to an Exempt Person, does not beneficially own twenty percent (20%) or more of the Common Shares of the Company then outstanding). Notwithstanding the foregoing, (i) if the Board determines in good faith that a Person who would otherwise be an “Acquiring Person,” as defined pursuant to the foregoing provisions of this paragraph (a), has become such inadvertently (including, without limitation, because (A) such Person was unaware that it beneficially owned a percentage of the Common Shares that would otherwise cause such Person to be an “Acquiring Person,” as defined pursuant to the foregoing provisions of this paragraph (a), or (B) such Person was aware of the extent of the Common Shares it beneficially owned but had no actual knowledge of the consequences of such beneficial ownership under this Agreement) and without any intention of changing or influencing control of the Company, and if such Person divested or divests as promptly as practicable a sufficient number of Common Shares so that such Person would no longer be an “Acquiring Person,” as defined pursuant to the foregoing provisions of this paragraph (a), then such Person shall not be deemed to be or to have become an “Acquiring Person” for any purposes of this Agreement, including, without limitation, Section 1(jj) hereof; and (ii) if, as of the date hereof, any Person is the Beneficial Owner of fifteen percent (15%) or more of the Common Shares outstanding, such Person shall not be or become an “Acquiring Person,” as defined pursuant to the foregoing provisions of this paragraph (a), unless and until such time as such Person shall become the Beneficial Owner of additional Common Shares (other than pursuant to a dividend or distribution paid or made by the Company on the outstanding Common Shares in Common Shares or pursuant to a split or subdivision of the outstanding Common Shares), unless, upon becoming the Beneficial Owner of such additional Common Shares, such Person is not then the Beneficial Owner of fifteen percent (15%) or more of the Common Shares then outstanding.”

Section 2. “Agreement” as Amended. The term “Agreement” as used in the Agreement shall be deemed to refer to the Agreement as amended hereby, and all references to the Agreement shall be deemed to include this Amendment.

2

Section 3. Effectiveness. This Amendment shall be effective as of the date first written above, and except as set forth herein, the Agreement shall remain in full force and effect and otherwise shall be unaffected hereby. If any term, provision, covenant or restriction of this Amendment is held by a court of competent jurisdiction or other authority to be invalid, void or unenforceable, the remainder of the terms, provisions, covenants and restrictions of this Amendment shall remain in full force and effect and shall in no way be affected, impaired or invalidated.

Section 4. Counterparts. This Amendment may be executed in two or more counterparts, each of which shall be deemed an original but all of which together shall constitute one and the same instrument.

Section 5. Governing Law. This Amendment shall be deemed to be a contract made under the laws of the State of Delaware and for all purposes shall be governed by and construed in accordance with the laws of such State applicable to contracts to be made and performed entirely within such State.

[Signature Page Follows]

3

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