COST PLUS, INC. 2004 STOCK PLAN

Exhibit 4.1

COST PLUS, INC.

2004 STOCK PLAN

(Amended June 22, 2006)

(Amended June 18, 2009)

1. Purposes of the Plan . The purposes of this Stock Plan are:

Awards granted under the Plan may be Incentive Stock Options, Nonstatutory Stock Options, Restricted Stock, Stock Appreciation Rights, Performance Shares, Performance Units or Deferred Stock Units, as determined by the Administrator at the time of grant.

2. Definitions . As used herein, the following definitions shall apply:

(a) “ Administrator ” means the Board or any of its Committees as shall be administering the Plan, in accordance with Section 4 of the Plan.

(b) “ Annual Revenue ” means the Company’s or a business unit’s net sales for the Fiscal Year, determined in accordance with generally accepted accounting principles; provided, however, that prior to the Fiscal Year, the Administrator shall determine whether any significant item(s) shall be excluded or included from the calculation of Annual Revenue with respect to one or more Participants.

(c) “ Applicable Laws ” means the legal requirements relating to the administration of equity compensation plans under state corporate and securities laws and the Code.

(d) “ Award ” means, individually or collectively, a grant under the Plan of Options, Restricted Stock, Stock Appreciation Rights, Performance Shares, Performance Units or Deferred Stock Units.

(e) “ Award Agreement ” means the written agreement setting forth the terms and provisions applicable to each Award granted under the Plan. The Award Agreement is subject to the terms and conditions of the Plan.

(f) “ Awarded Stock ” means the Common Stock subject to an Award.

(g) “ Board ” means the Board of Directors of the Company.

(h) “ Cash Position ” means the Company’s level of cash and cash equivalents.

(i) “ Change of Control ” means the occurrence of any of the following events:

(i) The acquisition by any “person” (as such term is used in Sections 13(d) and 14(d) of the Exchange Act) (other than the Company or a person that directly or indirectly controls, is controlled by, or is under common control with, the Company) of the “beneficial ownership” (as defined in Rule 13d-3 under the Exchange Act), directly or indirectly, of securities of the Company representing fifty percent (50%) or more of the total voting power represented by the Company’s then outstanding voting securities;

(ii) A change in the composition of the Board occurring within a two-year period, as a result of which fewer than a majority of the directors are Incumbent Directors. “Incumbent Directors” shall mean Directors who either (A) are Directors as of the date hereof, or (B) are elected, or nominated for election, to the Board with the affirmative votes of at least a majority of the Incumbent Directors at the time of such election or nomination (but shall not include an individual not otherwise an Incumbent Director whose election or nomination is in connection with an actual or threatened proxy contest relating to the election of directors to the Company);

(iii) A merger or consolidation of the Company with any other corporation, other than a merger or consolidation which would result in the voting securities of the Company outstanding immediately prior thereto continuing to represent (either by remaining outstanding or by being converted into voting securities of the surviving entity) at least fifty percent (50%) of the total voting power represented by the voting securities of the Company or such surviving entity outstanding immediately after such merger or consolidation;

(iv) The approval by the shareholders of the Company of a plan of complete liquidation of the Company;

(v) The sale of all or substantially all of the assets of the Company determined on a consolidated basis; or

(vi) The complete liquidation or dissolution of the Company.

(j) “ Code ” means the Internal Revenue Code of 1986, as amended.

(k) “ Committee ” means a Committee appointed by the Board in accordance with Section 4 of the Plan.

(l) “ Common Stock ” means the Common Stock of the Company.

(m) “ Company ” means Cost Plus, Inc., a California corporation.

(n) “ Consultant ” means any person, including an advisor, engaged by the Company or a Parent or Subsidiary to render services and who is compensated for such services. The term Consultant shall not include Directors who are compensated by the Company only for their service as Directors.

(o) “ Deferred Stock Unit ” means a deferred stock unit Award granted to a Participant pursuant to Section 13.

(p) “ Director ” means a member of the Board.

-2-

(q) “ Disability ” means total and permanent disability as defined in Section 22(e)(3) of the Code.

(r) “ Earnings Per Share ” means as to any Fiscal Year, the Company’s or a business unit’s Net Income, divided by a weighted average number of common shares outstanding and dilutive common equivalent shares deemed outstanding, determined in accordance with generally accepted accounting principles.

(s) “ Employee ” means any person, including Officers and Directors, employed by the Company or any Parent or Subsidiary of the Company. A Service Provider shall not cease to be an Employee in the case of (i) any leave of absence approved by the Company or (ii) transfers between locations of the Company or between the Company, its Parent, any Subsidiary, or any successor. For purposes of Incentive Stock Options, no such leave may exceed ninety days, unless reemployment upon expiration of such leave is guaranteed by statute or contract. If reemployment upon expiration of a leave of absence approved by the Company is not so guaranteed, then three (3) months following the 91 ^st day of such leave any Incentive Stock Option held by the Participant shall cease to be treated as an Incentive Stock Option and shall be treated for tax purposes as a Nonstatutory Stock Option. Neither service as a Director nor payment of a director’s fee by the Company shall be sufficient to constitute “employment” by the Company.

(t) “ Exchange Act ” means the Securities Exchange Act of 1934, as amended.

(u) “ Fair Market Value ” means, as of any date, the value of Common Stock determined as follows:

(i) If the Common Stock is listed on any established stock exchange or a national market system, including without limitation the Nasdaq National Market of the National Association of Securities Dealers, Inc. Automated Quotation (“NASDAQ”) System, the Fair Market Value of a Share of Common Stock shall be the closing sales price for such stock (or the closing bid, if no sales were reported) as quoted on such system or exchange (or the exchange with the greatest volume of trading in Common Stock) on the day of determination, as reported in The Wall Street Journal or such other source as the Administrator deems reliable;

(ii) If the Common Stock is quoted on the NASDAQ System (but not on the Nasdaq National Market thereof) or is regularly quoted by a recognized securities dealer but selling prices are not reported, the Fair Market Value of a Share of Common Stock shall be the mean between the high bid and low asked prices for the Common Stock on the last market trading day prior to the day of determination, as reported in The Wall Street Journal or such other source as the Administrator deems reliable;

(iii) In the absence of an established market for the Common Stock, the Fair Market Value shall be determined in good faith by the Administrator.

(v) “ Fiscal Year ” means a fiscal year of the Company.

(w) “ Incentive Stock Option ” means an Option intended to qualify as an incentive stock option within the meaning of Section 422 of the Code and the regulations promulgated thereunder.

(x) “ Net Income ” means as to any Fiscal Year, the income after taxes of the Company for the Fiscal Year determined in accordance with generally accepted accounting principles, provided that prior to the Fiscal Year, the Administrator shall determine whether any significant item(s) shall be included or excluded from the calculation of Net Income with respect to one or more Participants.

-3-

(y) “ Nonstatutory Stock Option ” means an Option not intended to qualify as an Incentive Stock Option.

(z) “ Notice of Grant ” means a written notice evidencing certain terms and conditions of an individual Award. The Notice of Grant is part of the Option Agreement.

(aa) “ Officer ” means a person who is an officer of the Company within the meaning of Section 16 of the Exchange Act and the rules and regulations promulgated thereunder.

(bb) “ Operating Cash Flow ” means the Company’s or a business unit’s sum of Net Income plus depreciation and amortization less capital expenditures plus changes in working capital comprised of accounts receivable, inventories, other current assets, trade accounts payable, accrued expenses, product warranty, advance payments from customers and long-term accrued expenses, determined in accordance with generally acceptable accounting principles.

(cc) “ Operating Income ” means the Company’s or a business unit’s income from operations but excluding any unusual items, determined in accordance with generally accepted accounting principles.

(dd) “ Option ” means a stock option granted pursuant to the Plan.

(ee) “ Option Agreement ” means a written agreement between the Company and a Participant evidencing the terms and conditions of an individual Option grant. The Option Agreement is subject to the terms and conditions of the Plan.

(ff) “ Parent ” means a “parent corporation”, whether now or hereafter existing, as defined in Section 424(e) of the Code.

(gg) “ Participant ” means the holder of an outstanding Award granted under the Plan.

(hh) “ Performance Goals ” means the goal(s) (or combined goal(s)) determined by the Administrator (in its discretion) to be applicable to a Participant with respect to an Award. As determined by the Administrator, the Performance Goals applicable to an Award may provide for a targeted level or levels of achievement using one or more of the following measures: (a) Annual Revenue, (b) Cash Position, (c) Earnings Per Share, (d) Net Income, (e) Operating Cash Flow, (f) Operating Income, (g) Return on Assets, (h) Return on Equity, (i) Return on Sales, and (j) Total Shareholder Return. The Performance Goals may differ from Participant to Participant and from Award to Award.

(ii) “ Performance Share ” means a performance share Award granted to a Participant pursuant to Section 11.

(jj) “ Performance Unit ” means a performance unit Award granted to a Participant pursuant to Section 12.

(kk) “ Per Share Strike Price ” means, with respect to each Option or SAR, the per share exercise price.

(ll) “ Plan ” means this 2004 Stock Plan.

(mm) “ Restricted Stock ” means Shares granted pursuant to Section 10 of the Plan.

-4-

(nn) “ Retirement ” means a Participant’s voluntary retirement at or after age 65 (or, with the consent of the Plan Administrator, in its sole discretion, age 55).

(oo) “ Return on Assets ” means the percentage equal to the Company’s or a business unit’s Operating Income before incentive compensation, divided by average net Company or business unit, as applicable, assets, determined in accordance with generally accepted accounting principles.

(pp) “ Return on Equity ” means the percentage equal to the Company’s Net Income divided by average shareholder’s equity, determined in accordance with generally accepted accounting principles.

(qq) “ Return on Sales ” means the percentage equal to the Company’s or a business unit’s Operating Income before incentive compensation, divided by the Company’s or the business unit’s, as applicable, revenue, determined in accordance with generally accepted accounting principles.

(rr) “ Rule 16b-3 ” means Rule 16b-3 of the Exchange Act or any successor to Rule 16b-3, as in effect when discretion is being exercised with respect to the Plan.

(ss) “ Section 16(b) ” means Section 16(b) of the Securities Exchange Act of 1934, as amended.

(tt) “ Service Provider ” means an Employee or Consultant.

(uu) “ Share ” means a share of the Common Stock, as adjusted in accordance with Section 16 of the Plan.

(vv) “ Stock Appreciation Right ” or “ SAR ” means an Award granted pursuant to Section 9 hereof.

(ww) “ Subsidiary ” means a “subsidiary corporation”, whether now or hereafter existing, as defined in Section 424(f) of the Code.

(xx) “ Total Shareholder Return ” means the total return (change in share price plus reinvestment of any dividends) of a Share.

3. Stock Subject to the Plan . Subject to the provisions of Section 16 of the Plan, the maximum aggregate number of Shares which may be issued under the Plan is 3,400,000 Shares plus any Shares remaining available for issuance pursuant to the Company’s 1995 Stock Plan as of the date upon which this Plan was initially approved by shareholders in 2004, up to a maximum of 100,000 Shares, plus any shares subject to any outstanding options under the Company’s 1995 Stock Option Plan that subsequently expire unexercised, up to a maximum of an additional 800,000 Shares; provided, however, that in no event shall more than 30% of the Stock remaining issuable under the Plan as of the date of obtaining shareholder approval for an additional 1,500,000 shares to be added to the Plan in 2009 and 30% of the Shares subsequently added to the Plan by virtue of outstanding 1995 Stock Option Plan options expiring unexercised be issued pursuant to Awards with an exercise price or purchase price that is less than 100% of Fair Market Value on the date of grant. The Shares may be authorized, but unissued, or reacquired Common Stock.

If an Award expires or becomes unexercisable without having been exercised in full, or, with respect to Restricted Stock, Performance Shares, Performance Units or Deferred Stock Units, is forfeited to or repurchased by the Company, the unpurchased Shares (or for Awards other than Options and SARs, the

-5-

forfeited or repurchased shares) which were subject thereto shall become available for future grant or sale under the Plan (unless the Plan has terminated). With respect to SARs, only shares actually issued pursuant to an SAR shall cease to be available under the Plan; all remaining shares under SARs shall remain available for future grant or sale under the Plan (unless the Plan has terminated). However, Shares that have actually been issued under the Plan under any Award shall not be returned to the Plan and shall not become available for future distribution under the Plan; provided, however, that if Shares of Restricted Stock, Performance Shares, Performance Units or Deferred Stock Units are repurchased by the Company at their original purchase price or are forfeited to the Company, such Shares shall become available for future grant under the Plan. To the extent an Award under the Plan is paid out in cash rather than stock, such cash payment shall not result in reducing the number of Shares available for issuance under the Plan.

4. Administration of the Plan .

(a) Procedure .

(i) Multiple Administrative Bodies . The Plan may be administered by different Committees with respect to different groups of Service Providers.

(ii) Section 162(m) . To the extent that the Administrator determines it to be desirable to qualify Options granted hereunder as “performance-based compensation” within the meaning of Section 162(m) of the Code, the Plan shall be administered by a Committee of two or more “outside directors” within the meaning of Section 162(m) of the Code.

(iii) Rule 16b-3 . To the extent desirable to qualify transactions hereunder as exempt under Rule 16b-3, the transactions contemplated hereunder shall be structured to satisfy the requirements for exemption under Rule 16b-3.

(iv) Other Administration . Other than as provided above, the Plan shall be administered by (A) the Board or (B) a Committee, which committee shall be constituted to satisfy Applicable Laws.

(b) Powers of the Administrator . Subject to the provisions of the Plan, and in the case of a Committee, subject to the specific duties delegated by the Board to such Committee, the Administrator shall have the authority, in its discretion:

(i) to determine the Fair Market Value of the Common Stock, in accordance with Section 2(u) of the Plan;

(ii) to select the Service Providers to whom Awards may be granted hereunder;

(iii) to determine whether and to what extent Awards or any combination thereof, are granted hereunder;

(iv) to determine the number of shares of Common Stock to be covered by each Award granted hereunder;

(v) to approve forms of agreement for use under the Plan;

(vi) to determine the terms and conditions, not inconsistent with the terms of the Plan, of any award granted hereunder. Such terms and conditions include, but are not limited to, the exercise

-6-

price, the time or times when Options or SARs may be exercised or other Awards vest (which may be based on performance criteria), any vesting acceleration or waiver of forfeiture restrictions, and any restriction or limitation regarding any Award or the shares of Common Stock relating thereto, based in each case on such factors as the Administrator, in its sole discretion, shall determine;

(vii) to construe and interpret the terms of the Plan and Awards;

(viii) to prescribe, amend and rescind rules and regulations relating to the Plan, including rules and regulations relating to sub-plans established for the purpose of qualifying for preferred tax treatment under foreign tax laws;

(ix) to modify or amend each Award (subject to Section 18(c) of the Plan), including the discretionary authority to extend the post-termination exercisability period of Options and SARs longer than is otherwise provided for in the Plan;

(x) to authorize any person to execute on behalf of the Company any instrument required to effect the grant of an Option or Stock Appreciation previously granted by the Administrator;

(xi) to allow Participants to satisfy withholding tax obligations by electing to have the Company withhold from the Shares or cash to be issued upon exercise or vesting of an Award (or distribution of a Deferred Stock Unit) that number of Shares or cash having a Fair Market Value equal to the minimum amount required to be withheld. The Fair Market Value of any Shares to be withheld shall be determined on the date that the amount of tax to be withheld is to be determined. All elections by a Participant to have Shares or cash withheld for this purpose shall be made in such form and under such conditions as the Administrator may deem necessary or advisable;

(xii) to determine the terms and restrictions applicable to Awards; and

(xiii) to make all other determinations deemed necessary or advisable for administering the Plan.

(c) Effect of Administrator’s Decision . The Administrator’s decisions, determinations and interpretations shall be final and binding on all Participants and any other holders of Awards.

5. Eligibility . Restricted Stock, Performance Shares, Performance Units, Stock Appreciation Rights, Deferred Stock Units and Nonstatutory Stock Options may be granted to Service Providers. Incentive Stock Options may be granted only to Employees.

6. Limitations .

(a) Each Option shall be designated in the Notice of Grant as either an Incentive Stock Option or a Nonstatutory Stock Option. However, notwithstanding such designations, to the extent that the aggregate Fair Market Value:

(i) of Shares subject to a Participant’s Incentive Stock Options granted by the Company, any Parent or Subsidiary, which

(ii) become exercisable for the first time during any calendar year (under all plans of the Company or any Parent or Subsidiary)

-7-

exceeds $100,000, such excess Options shall be treated as Nonstatutory Stock Options. For purposes of this Section 6(a), Incentive Stock Options shall be taken into account in the order in which they were granted, and the Fair Market Value of the Shares shall be determined as of the time of grant.

(b) Neither the Plan nor any Award shall confer upon a Participant any right with respect to continuing the Participant’s employment with the Company or its Subsidiaries, nor shall they interfere in any way with the Participant’s right or the Company’s or Subsidiary’s right, as the case may be, to terminate such employment at any time, with or without cause or notice.

(c) The following limitations shall apply to grants of Options and Stock Appreciation Rights to Employees:

(i) No Employee shall be granted, in any fiscal year of the Company, Options and Stock Appreciation Rights to purchase more than 300,000 Shares.

(ii) The foregoing limitations shall be adjusted proportionately in connection with any change in