Exhibit 10.1

EXECUTION VERSION

This AGREEMENT, dated as of September 28, 2011 (this “Agreement”), is by and among Family Dollar Stores, Inc., a Delaware corporation (the “Company”), and the other entities and persons signatory hereto (collectively, the “Investors”).

WHEREAS, the Board of Directors of the Company (the “Board”) intends to (i) increase the size of the Board from ten (10) to eleven (11) members and (ii) appoint Edward P. Garden (“EPG”) as a director to fill the newly created vacancy, with a term expiring at the Company’s annual stockholders’ meeting occurring during fiscal year 2012 (the “2012 Annual Meeting”);

WHEREAS, at the 2012 Annual Meeting and the Company’s annual stockholders’ meeting occurring during fiscal year 2013 (the “2013 Annual Meeting” and, together with the 2012 Annual Meeting, the “2012 and 2013 Annual Meetings”), the Board intends to (i) nominate EPG for election as a member of the Board with respective terms expiring at the first annual stockholders’ meeting following each such meeting and (ii) recommend that the shareholders of the Company vote to elect EPG as a director of the Company at the 2012 and 2013 Annual Meetings;

WHEREAS, on the date hereof the Investors Economically Own (as defined below) the interests in shares, each with a $0.10 par value, of the Company’s common stock (the “Common Stock”) specified on Schedule A of this Agreement;

WHEREAS, the Investors support the appointment of EPG to the Board and his nomination and election at the 2012 and 2013 Annual Meetings; and

WHEREAS, concurrently with the execution and delivery of this Agreement, the Investors are withdrawing their previously announced proposal to acquire the Company as disclosed previously by the Investors in a filing on Schedule 13D;

NOW, THEREFORE, in consideration of the mutual covenants and agreements contained herein, and for other good and valuable consideration, the receipt and sufficiency of which is hereby acknowledged, the parties hereto agree as follows:

ARTICLE I

REPRESENTATIONS

SECTION 1.1 Authority; Binding Agreement. (a) The Company hereby represents that this Agreement and the performance by the Company of its obligations hereunder (i) has been duly authorized, executed and delivered by the Company, and is a valid and binding obligation of the Company, enforceable against the Company in accordance with its terms, (ii) does not require the approval of the shareholders of the Company and (iii) does not and will not violate any law, any order of any court or other agency of government, the certificate of incorporation of the Company or the bylaws of the Company, or any stock exchange rule or regulation, or any provision of any indenture, agreement or other instrument to which the Company or any of its properties or assets is bound, or conflict with, result in a breach of or constitute (with due notice or lapse of time or both) a default under any such indenture, agreement or other instrument, or result in the creation or imposition of, or give rise to, any lien, charge, restriction, claim,

1

encumbrance or adverse penalty of any nature whatsoever pursuant to any such indenture, agreement or other instrument.

(b) Each of the Investors represents and warrants that this Agreement and the performance by such Investor of its obligations hereunder (i) has been duly authorized, executed and delivered by such Investor, and is a valid and binding obligation of such Investor, enforceable against such Investor in accordance with its terms, (ii) does not require approval by any owners or holders of any equity interest in such Investor (except as has already been obtained) and (iii) does not and will not violate any law, any order of any court or other agency of government, the charter or other organizational documents of such Investor, as amended, or any provision of any agreement or other instrument to which such Investor or any of its properties or assets is bound, or conflict with, result in a breach of or constitute (with due notice or lapse of time or both) a default under any such agreement or other instrument, or result in the creation or imposition of, or give rise to, any lien, charge, restriction, claim, encumbrance or adverse penalty of any nature whatsoever pursuant to any such agreement or instrument.

SECTION 1.2 Interests in Common Stock. The Investors hereby represent and warrant that, as of the date hereof, they and their Affiliates (as such term is hereinafter defined) are, collectively, the Economic Owners of such number of shares of Common Stock as is accurately and completely set forth (including, without limitation, as to the form of ownership) on Schedule A hereto, and none of the Investors or any of their Affiliates Economically Own any other securities of the Company. During the Standstill Period, Trian Fund Management, L.P. (“TFM”), on behalf of the Investors, shall promptly (and in any event within three business days) notify the Company in writing (a) upon the Investors, together with their Affiliates, ceasing to own, in the aggregate, the Minimum Percentage of shares of Common Stock and (b) upon the Investors, together with their Affiliates, becoming the Economic Owners, in the aggregate, of more than 9.9% of the then outstanding shares of Common Stock (based, in the case of this clause (b), on the number of outstanding shares of Common Stock most recently indicated by the Company as outstanding in (x) any of the Company’s Annual Report on Form 10-K, Quarterly Report on Form 10-Q or definitive proxy statement on Schedule 14A, in each case as filed by the Company with the Securities and Exchange Commission (the “SEC”) or (y) a written notice by the Company to TFM). At any time during the Standstill Period in which (i) the Investors, together with their Affiliates, own, in the aggregate, at least the Minimum Percentage of shares of Common Stock and (ii) the Investors no longer report on Schedule 13D with the SEC the Investors’ Beneficial Ownership of Common Stock, TFM, on behalf of the Investors shall, upon request of the Company (which request shall not be made more than once during any quarterly period), promptly (and no later than five business days after the request is made) provide the Company with a written report specifying the number of shares of Common Stock Economically Owned, in the aggregate, by the Investors together with their Affiliates, as of the close of business on the date immediately preceding such request.

SECTION 1.3 Defined Terms. For purposes of this Agreement

(a) The term “Affiliate” has the meaning set forth in Rule 12b-2 promulgated by the SEC under the Securities Exchange Act of 1934, as amended (the “Exchange Act”); provided, that the term “Affiliate” shall not include any portfolio or operating company of the Investors for which all of the following conditions are satisfied: (i) whose equity securities are registered

2

under the Exchange Act (or are publicly traded in a foreign jurisdiction), (ii) as to which the Investors and their Affiliates own less than a majority of the total voting power of all outstanding voting securities and do not have representatives or designees who occupy a majority of the seats on the board of directors or other similar governing body of such portfolio or operating company and do not otherwise control (as the term “control” is defined in Rule 12b-2 promulgated by the SEC under the Exchange Act) such portfolio or operating company, and (iii) to which no non-public information about the Company has been made available by the Director Designee or any of the Investors or their Affiliates. For purposes of this definition, it is hereby acknowledged and agreed that funds or accounts as to which TFM or any Affiliate thereof has voting or investment power over shares of the Company’s Common Stock shall be deemed an “Affiliate” of TFM. For purposes of this Agreement, the Investors, on the one hand, and the Company, on the other, shall not be deemed to be Affiliates of each other.

(b) The terms “Beneficial Owner,” “Beneficially Own” and “Beneficial Ownership” shall have the same meanings as set forth in Rule 13d-3 (“Rule 13d-3”) promulgated by the SEC under the Exchange Act. The terms “Economic Owner,” “Economically Own” and “Economic Ownership” shall have the same meanings as “Beneficial Owner,” “Beneficially Own” and “Beneficial Ownership” except that a person will also be deemed to “Economically Own,” to be the “Economic Owner” and to have “Economic Ownership” of (i) all shares of Common Stock which such person has the right to acquire pursuant to the exercise of any rights in connection with any securities or any agreement, regardless of when such rights may be exercised and whether they are conditional, and (ii) all shares of Common Stock in which such person has any economic interest, including, without limitation, pursuant to a cash settled call option or other derivative security, contract or instrument in any way related to the price of shares of Common Stock.

(c) The term “Director Designee” shall mean EPG, or any replacement agreed upon by the Company and TFM in accordance with and subject to Section 2.1(e).

(d) “Extraordinary Matter” means (i) any merger, consolidation, share exchange, recapitalization, or other business combination, in each case as a result of which the holders of the Common Stock of the Company immediately prior to the consummation of such transaction would cease to own at least a majority of the outstanding shares of common stock of the resulting company (or, if such resulting company is a subsidiary, then the ultimate parent company) or (ii) any liquidation, dissolution or sale of all or substantially all of the assets of the Company, in each case referred to in (i) or (ii) that is subject to approval by the stockholders of the Company. For the avoidance of doubt, “Extraordinary Matter” does not include a proxy contest or consent solicitation with respect to the election of directors.

(e) References to “fiscal year” mean the Company’s fiscal year. The 12-month period ended August 27, 2011 is fiscal year 2011.

(f) “Minimum Percentage” means, as of any time, the ownership at such time and at all times during the prior 30 consecutive days, of the sum of: (x) Beneficial Ownership of Physical Shares of Common Stock equal to at least 3.0% of the outstanding shares of Common Stock and (y) Economic Ownership of shares of Common Stock equal to at least 2.0% of the outstanding shares of Common Stock (based, in the case of this definition, on the outstanding

3

shares of Common Stock being deemed to be the lower of (i) 120,241,598 and (ii) the number of shares of Common Stock most recently identified by the Company as outstanding in (x) any of the Company’s Annual Report on Form 10-K, Quarterly Report on Form 10-Q or definitive proxy statement on Schedule 14A, in each case as filed by the Company with the SEC or (y) a written notice by the Company to TFM).

(g) “Non-Election Date” means the 45th calendar day following the 2012 Annual Meeting or 2013 Annual Meeting, as the case may be, if, by such date, (i) the Director Designee is not elected at such meeting and (ii) the Director Designee has not been appointed to the Board with a term expiring at the Company’s next annual stockholders’ meeting. A “Non-Election Date” will not result if (A) nomination or appointment of the Director Designee in connection with the 2012 Annual Meeting or 2013 Annual Meeting, as the case may be, is not required by this Agreement or (B) the failure to elect or appoint the Director Designee results solely from such Director Designee’s resignation or refusal to serve.

(h) “Physical Shares” means, with respect to a person or entity, shares Beneficially Owned by such person or entity as to which such person or entity directly or indirectly has voting and investment power and which are held either of record by such person or entity or through a broker, dealer, agent, custodian or other nominee that is the holder of record of such shares. For the avoidance of doubt, it is understood that (i) “Physical Shares” shall not include shares Beneficially Owned by such person or entity solely as a result of the operation of (x) clauses (i) and (ii) of Section 1.3(b) or (y) Rule 13d-3(d)(1)(i)(A)-(B), and (ii) the fact that shares are held in a margin account or are pledged as collateral pursuant to customary loan documentation shall not result in such shares not being considered Physical Shares unless and until such shares are liquidated pursuant to a margin call or otherwise foreclosed upon by the applicable broker, lender or other third party.

(i) The “Standstill Period” means the period from the date of this Agreement through the earliest of:

(1) the date that is 60 calendar days prior to the first day of the notice period specified in the advance notice provision applicable to the Company’s annual stockholders’ meeting occurring during fiscal year 2014 (whether pursuant to applicable law or regulation or the Company’s certificate of incorporation or bylaws, each as may hereafter be amended);

(2) if the Company has materially breached this Agreement (including by failing to nominate the Director Designee for election at the 2012 Annual Meeting or 2013 Annual Meeting in violation of this Agreement, or failing to appoint a replacement to the Director Designee in accordance with and subject to Section 2.1(e), and within the timeframe set forth in Section 1.3(i)(5)), the date that TFM delivers to the Company written notice of termination of the Standstill Period specifying this Section 1.3(i)(2), provided that such notice will be effective and such termination of the Standstill Period shall occur only if (A) such notice of termination is delivered to the Company on or after the 15^th calendar day following TFM’s delivery to the Company of written notice describing the Company’s breach of this Agreement in reasonable detail and (B) the

4

Company, at the time of delivery of such notice of termination, has failed to cure such breach;

(3) if a Non-Election Date occurs, the date (on or after the Non-Election Date) on which TFM delivers to the Company written notice of termination of the Standstill Period specifying this Section 1.3(i)(3);

(4) if the Director Designee is removed from the Board (but not including removal of the Director Designee (A) following such Director Designee’s failure to resign in accordance with Section 2.1(a), (B) in connection with such Director Designee’s required resignation pursuant to Section 2.1(a) or (C) under the circumstances described in Section 1.3(i)(5)(A)), the date (on or after the date of such removal) on which TFM delivers to the Company written notice of termination of the Standstill Period specifying this Section 1.3(i)(4); or

(5) if both (A) the then-current Director Designee voluntarily resigns as a director of the Company or is unable to serve as a director of the Company as a result of his or her death or incapacity and (B) either (i) TFM complies with Section 2.1(e), but the Company and TFM fail to agree on a replacement in accordance with Section 2.1(e) within 90 calendar days following the date that the last Director Designee ceased to be a director of the Company or (ii) the Board fails to appoint the agreed replacement to the Board within 90 calendar days following the date that the last Director Designee ceased to be a director of the Company, the date (on or after the expiration of such 90 calendar days) on which TFM delivers to the Company written notice of termination of the Standstill Period specifying this Section 1.3(i)(5).

ARTICLE II

COVENANTS

SECTION 2.1 Director. (a) As promptly as practicable following the date of this Agreement, the Board shall (i) increase the size of the Board from ten (10) to eleven (11) directors and (ii) appoint EPG as a director of the Company with a term expiring at the 2012 Annual Meeting. By entering into this Agreement, the Director Designee hereby irrevocably agrees to resign as a member of the Board, upon the earlier of (x) the date that both (I) either (A) the Standstill Period has terminated or (B) the Investors, together with their Affiliates, do not own, in the aggregate, the Minimum Percentage (each of the foregoing (A) and (B), a “Triggering Event”) and (II) five calendar days have elapsed since the Triggering Event and the Board has requested in writing the Director Designee’s resignation, in which case the resignation shall take effect at the time the Board has delivered such request to the Director Designee and TFM, and (y) the date that the Board delivers a written request to the Director Designee and TFM for the Director Designee’s resignation under the circumstances described in, and in accordance with, Section 3.1(b). For the avoidance of doubt, the Company may at any time and from time to time increase or decrease the size of the Board or change its composition, provided that such increase or decrease may not affect the tenure of the Director Designee.

5

(b) The Company agrees that, provided that the Standstill Period has not terminated, the Board will:

(1) at the 2012 and 2013 Annual Meetings, nominate the Director Designee for election as a director of the Company (other than in the case of such Director Designee’s refusal or inability to serve), together with the other persons so nominated on the Company’s slate in the Company’s proxy statement or proxy card for such annual meetings, with terms expiring at the Company’s next annual stockholders’ meeting following the 2012 and 2013 Annual Meetings, respectively; and

(2) recommend that the shareholders of the Company vote to elect the Director Designee as a director of the Company at the 2012 and 2013 Annual Meetings.

(c) The Company shall use reasonable best efforts (which shall include the solicitation of proxies) to ensure that the Director Designee is elected at the 2012 and 2013 Annual Meetings, provided that the Standstill Period has not terminated prior to the date of such meeting.

(d) If (i) the Company fails to nominate the Director Designee and such failure constitutes a violation of the Company’s obligations under this Agreement and (ii) the period under the Company’s bylaws for nomination of directors by stockholders has expired, or has less than 20 calendar days remaining, on the date (the “Disclosure Date”) that is the earlier of (x) the date that the Company gives written notice to the Director Designee that the Company is nominating a slate that excludes the Director Designee in a manner that constitutes a violation of the Company’s obligations under this Agreement and (y) the date that the Company publicly announces a slate of director nominees that excludes the Director Designee in a manner that constitutes a violation of the Company’s obligations under this Agreement, then the Company will (I) extend the deadline under the bylaws during which the Investors may nominate directors on and subject to the terms of the bylaws (other than the time period for submitting nominations) so that the period from the Disclosure Date through the extended deadline is at least 20 calendar days and (II) not hold the annual meeting at which such slate is up for election until at least 45 calendar days after such extended deadline.

(e) The Company and the Investors agree that EPG, Nelson Peltz (“NP”) and Peter W. May (“PWM”) are agreed upon and acceptable replacements for the Director Designee (subject to the Board’s good faith completion of its customary due diligence process, including review of a Directors’ and Officers’ questionnaire, background check and interviews) in the event the then-current Director Designee voluntarily resigns as a director of the Company or is unable to serve as a director of the Company due to death or incapacity. The Company shall not unreasonably withhold, delay or condition its consent to a replacement for the Director Designee requested by TFM, provided that if any of EPG, NP or PWM is not unable to serve due to death or incapacity, then TFM shall be obligated to agree on at least one of EPG, NP or PWM as a replacement for the Director Designee if so requested by the Company. No person, other than EPG, NP or PWM (each of whom has executed this Agreement), may be a Director Designee, unless he or she has executed a joinder to this Agreement solely with respect to the obligations set forth in the second sentence of Section 2.1(a).

6

SECTION 2.2 Voting Provisions. During the Standstill Period, the Investors shall cause, and shall cause their respective Affiliates to cause, all shares of Common Stock for which they have the right to vote to be present for quorum purposes and to be voted at any meeting of shareholders or at any adjournments or postponements thereof, and to consent in connection with any action by consent in lieu of a meeting, (i) in favor of each director nominated and recommended by the Board for election at any such meeting, and (ii) against any shareholder nominations for director which are not approved and recommended by the Board for election at any such meeting and against any proposals or resolutions to remove any member of the Board.

SECTION 2.3 Actions by the Investors. Each of the Investors agrees that, during the Standstill Period, it shall not, and shall cause its Affiliates not to, unless specifically requested or authorized in writing by a resolution of the Board, directly or indirectly:

(a) purchase or cause to be purchased or otherwise acquire or agree to acquire Economic Ownership of (i) any Common Stock, if in any such case, immediately after the taking of such action the Investors, together with their respective Affiliates, would, in the aggregate, Economically Own more than 9.9% of the then outstanding shares of Common Stock (such Economic Ownership in excess of 9.9% of the then outstanding shares of Common Stock, the “Excess Amount”) (the parties agree that (A) it shall not be a breach of this Section 2.3(a) if (1) the Investors, together with their Affiliates, inadvertently Economically Own the Excess Amount, if as soon as practicable the Investors, together with their Affiliates, divest themselves of Economic Ownership of sufficient shares so that they cease to Economically Own any Excess Amount or (2) the Investors, together with their Affiliates, Economically Own the Excess Amount solely as a result of share purchases, reverse share splits or other actions taken by the Company that, by reducing the number of shares outstanding (or, in the event the Company does not have a shareholder rights plan in effect or has a shareholder rights plan in effect that provides for an Economic Ownership threshold for purposes of qualifying as an “Acquiring Person” that is greater than 10%, issuing shares of Common Stock to the Director Designee pursuant to the Company’s director compensation plan), cause the Investors, together with their Affiliates, to Economically Own the Excess Amount, provided that the Economic Ownership of the Investors, together with their Affiliates, does not further increase thereafter, other than (x) solely as a result of further corporate actions taken by the Company or (y) an increase in Economic Ownership not covered by the immediately preceding clause (x) that does not exceed an additional 1% of Common Stock then outstanding, and (B) for purposes of any calculation under this Section 2.3(a), the number of shares of Common Stock then outstanding shall be the number most recently identified by the Company as outstanding in (1) any of the Company’s Annual Report on Form 10-K, Quarterly Report on Form 10-Q or definitive proxy statement on Schedule 14A, in each case as filed by the Company with the SEC or (2) a written notice by the Company to TFM), or (ii) any other securities issued by the Company;

(b) form, join, or in any other way participate in, a “partnership, limited partnership, syndicate or other group” within the meaning of Section 13(d)(3) of the Exchange Act with respect to the Common Stock, or deposit any shares of Common Stock in a voting trust or similar arrangement, or subject any shares of Common Stock to any voting agreement or pooling arrangement, or grant any proxy, designation or consent with respect to any shares of Common Stock (other than to a designated representative of the Company pursuant to a proxy or consent solicitation on behalf of the Board), other than solely with other Investors or one or more

7

Affiliates (other than portfolio or operating companies) of an Investor with respect to the shares of Common Stock acquired in compliance with paragraph (a) above or to the extent such a group may be deemed to result with the Company or any of its Affiliates as a result of this Agreement (it being understood that the holding by persons or entities of shares of Common Stock in accounts or through funds not managed or controlled by an Investor or any Affiliate of any Investor shall not give rise to a violation of this Section 2.3(b) solely by virtue of the fact that such persons or entities, in addition to holding such shares in such manner, are investors in funds and accounts managed by an Investor or any of its Affiliates and, in their capacity as such, are or may be deemed to be members of a “group” with the Investors within the meaning of Section 13(d)(3) of the Exchange Act with respect to the Common Stock; provided there does not exist as between such persons or entities, on the one hand, and the Investors or any of its Affiliates, on the other hand, any agreement, arrangement or understanding with respect to any action that would otherwise be prohibited by this Section 2.3);

(c) solicit proxies, designations or written consents of shareholders, or conduct any binding or nonbinding referendum with respect to Common Stock, or make or in any way participate in any “solicitation” of any “proxy” within the meaning of Rule 14a-1 promulgated by the SEC under the Exchange Act (but without regard to the exclusion set forth in Rule 14a-1(l)(2)(iv) from the definition of “solicitation”) to vote any shares of Common Stock with respect to any matter, or become a participant in any contested solicitation for the election of directors with respect to the Company (as such terms are defined or used in the Exchange Act and the Rules promulgated thereunder), other than solicitations or acting as a participant in support of the voting obligations of the Investors and their Affiliates pursuant to Section 2.2;

(d) seek to call, request the call of, or call a special meeting of the shareholders of the Company, or make or seek to make a shareholder proposal (whether pursuant to Rule 14a-8 under the Exchange Act or otherwise) at any meeting of the shareholders of the Company or in connection with any action by consent in lieu of a meeting, or make a request for a list of the Company’s shareholders, or seek election to the Board or seek to place a representative on the Board (other than as expressly set forth in Section 2.1 and Section 2.2), or seek the removal of any director from the Board, or otherwise acting alone or in concert with others, seek to control or influence the governance or policies of the Company;

(e) propose, offer or participate in (i) any effort to acquire the Company or any of its subsidiaries or any material assets or operations of the Company or any of its subsidiaries, (ii) any effort to engage in a transaction or enter into any agreement that would result in Economic Ownership by any person or entity (whether or not an Investor) or group (as defined in Section 13(d)(3) of the Exchange Act) of more than 9.9% of the outstanding shares of Common Stock at any time or outstanding voting power of the Company at any time, (iii) any tender offer, exchange offer, merger, acquisition, share exchange or other business combination or “change in control” (as such term is used in Item 6 of Schedule 14A) transaction involving the Company or any of its subsidiaries, or (iv) any recapitalization, restructuring, liquidation, disposition, dissolution or other extraordinary transaction involving the Company, any of its subsidiaries or any material portion of their businesses;

(f) publicly disclose, or cause or facilitate the public disclosure (including without limitation the filing of any document or report with the SEC or any other governmental agency

8

or any disclosure to any journalist, member of the media or securities analyst) of, any intent, purpose, plan or proposal to obtain any waiver, consent under, or amendment of, any of the provisions of Section 2.2 or Section 2.3, or otherwise (i) seek in any manner to obtain any waiver, consent under, or amendment of, any provision of this Agreement or (ii) bring any action or otherwise act to contest the validity or enforceability of Section 2.2 or Section 2.3 or seek a release from the restrictions or obligations contained in Section 2.2 or Section 2.3 (it being understood, however, that the Board may adopt a resolution that modifies or waives Section 2.2 or Section 2.3);

(g) make or issue or cause to be made or issued any public disclosure, announcement or statement (including without limitation the filing of any document or report with the SEC or any other governmental agency or any disclosure to any journalist, member of the media or securities analyst) (i) in support of any solicitation described in paragraph (c) above (other than solicitations on behalf of the Board), (ii) in support of any matter described in paragraph (d) above, (iii) concerning any potential matter described in paragraph (e) above or (iv) negatively or disparagingly commenting about the Company or any of the Company’s directors, officers, key employees, businesses, operations or strategic plans or strategic directions; or

(h) enter into any discussions, negotiations, agreements or understandings with any person or entity with respect to the foregoing, or advise, assist, encourage, support or seek to persuade others to take any action with respect to any of the foregoing, or act in concert with others or as part of a group (within the meaning of Section 13(d)(3) of the Exchange Act) with respect to any of the foregoing.

In the event the Company has announced or entered into a binding agreement providing for, or has recommended that its shareholders support, an Extraordinary Matter, the provisions of this Section 2.3 shall not operate to prevent the Investors from proposing or taking any actions in furtherance of, or consummating, a competing Extraordinary Matter, provided that all of the other provisions of this Agreement shall continue in full force and effect.

Notwithstanding anything herein to the contrary, nothing in this Section 2.3 shall be deemed to in any way restrict or limit: (i) the Director Designee, in his capacity as a member of the Board, from confidentially expressing or advocating for his or her views to the Company, the Board, officers of the Company, other directors, or at Board meetings and by voting in his or her capacity as a director; (ii) the Investors or their Affiliates from (A) discussing any matter confidentially with the Company, the Board, officers of the Company or any directors of the Company solely to the extent that, without the prior written consent of the Company, such discussions (1) are not publicly disclosed, and would not reasonably be expected to require public disclosure, (including, without limitation, in any document or report filed with the SEC) by an Investor or any Affiliate of any Investor at or around the time such discussions take place, and (2) are not reasonably expected to require public disclosure (including, without limitation, in any document or report filed with the SEC) by the Company at or around the time such discussions take place, (B) voting their shares of Common Stock on any matter brought before the shareholders of the Company in any manner that they choose, other than as expressly provided in Section 2.2, (C) selling any shares of Common Stock, including in response to a Company or third-party tender offer or exchange offer, or (D) buying any shares of Common Stock other than as expressly provided in Section 2.3(a) (and Section 2.3(h) to the extent relating

9

to Section 2.3(a)); or (iii) the Director Designee or the Investors from communicating, on a confidential basis, with attorneys, accountants or financial advisors (excluding any advisor who has taken, takes or is expected by the Investors to take, any action that if taken by the Investors would violate Section 2.3), or as otherwise required by law.

SECTION 2.4 Additional Preparations by the Investors. (a) As of the date of this Agreement, the Investors are not engaged in any discussions or negotiations and do not have any agreements or understandings, whether or not legally enforceable, concerning the acquisition of Economic Ownership of any Common Stock, other than with investors or potential investors in funds and accounts managed or to be managed by TFM or an Affiliate thereof.

(b) The Investors hereby withdraw their previously announced proposal to acquire the Company as disclosed previously by the Investors in a filing on Schedule 13D, and shall promptly file an amended Schedule 13D substantially in the form previously reviewed by the Company. In addition, the Company shall promptly file a current report on Form 8-K that describes this agreement substantially in the form previously reviewed by TFM.

SECTION 2.5 Accommodations for Director Designee. The Company acknowledges that:

(a) the acquisition by the Investors of Economic Ownership of shares of Common Stock through privately negotiated back-to-back call and put transactions pursuant to which, simultaneously with the purchase of each call option, the Investors also sell a put option for the same number of shares of Common Stock and which may, at the option of the Investors, be settled in shares of Common Stock, or any similar transaction that results in the Investors Economically Owning the equivalent of shares of Common Stock, cash settled call options or other derivative securities, contracts or instruments related to the price of shares of Common Stock, holding shares of Common Stock in margin accounts or otherwise pledging shares of Common Stock as collateral security will not violate, or result in the breach of, any of the Company’s policies applicable to directors of the Company, including, without limitation, the Company’s Board of Directors Code of Business Conduct, The Insider Trading Compliance Policy, The Code of Business Conduct and The Corporate Governance Guidelines (for the avoidance of doubt, the foregoing does not apply with respect to and is not a waiver of the Company’s policies relating to trading windows, reporting, insider trading, short sales or pre-clearance);

(b) the service by a principal of the Investors on the board of H.J. Heinz Company shall not, by itself, violate any of the Company’s policies applicable to directors of the Company, including, without limitation, the Company’s Board of Directors Code of Business Conduct, The Insider Trading Compliance Policy, The Code of Business Conduct and The Corporate Governance Guidelines (for the avoidance of doubt, the foregoing does not waive any duties or obligations arising under applicable law);

(c) as of the date of this Agreement, that EPG qualifies as an “independent director” for purposes of Section 303A of the Listed Company Manual of the New York Stock Exchange;

10

(d) the Director Designee may serve on the boards of up to six other public companies and the Board has taken all such action and has adopted all such resolutions necessary for the Board and the Company to permit, without any future authorization or consent of the Board (or any committee thereof), the Director Designee to serve concurrently at any time and from time to time as a director of up to six public companies (not including the Company) and such actions and resolutions shall remain in full force and effect during the Standstill Period; and

(e) for purposes of determining whether the Director Designee is in compliance with any stock ownership guidelines of the Company relating to the amount of shares of Common Stock required to be owned by the Company’s directors, the Physical Shares of Common Stock Beneficially Owned by the Investors together with their Affiliates shall be included in any such determination.

SECTION 2.6 Publicity. Promptly after the execution of this Agreement, the Company and the Investors will issue a joint press release substantially in the form attached hereto as Schedule B (the “Joint Press Release”).

SECTION 2.7 Anti-Takeover Provisions. The Company agrees that, if during the Standstill Period it shall adopt any anti-takeover measure, including a shareholder rights plan, a board resolution or a bylaw amendment that would have an anti-takeover effect (other than a shareholder rights plan that provides for an Economic Ownership threshold for purposes of qualifying as an “Acquiring Person” that is less than 10%), it shall provide that such action will not prevent the Investors or their Affiliates from taking any actions during the Standstill Period that would not otherwise be prohibited during the Standstill Period by this Agreement.

SECTION 2.8 Affiliates. TFM shall cause each of its Affiliates and each Affiliate of each of the Investors that Economically Owns any shares of Common Stock to comply with this Agreement as if they were each an Investor.

ARTICLE III

OTHER PROVISIONS

SECTION 3.1 Specific Performance; Remedies. (a) Each party hereto hereby acknowledges and agrees, on behalf of itself and its Affiliates, that irreparable harm would occur in the event any of the provisions of this Agreement were not performed in accordance with their specific terms or were otherwise breached. It is accordingly agreed that the parties will be entitled to specific relief hereunder, including, without limitation, an injunction or injunctions to prevent and enjoin breaches of the provisions of this Agreement and to enforce specifically the terms and provisions hereof in the Chancery Court of the State of Delaware or if such court does not accept jurisdiction then any state or federal court in the State of Delaware, or, if such courts do not accept jurisdiction then any state or federal court in the State of New York, in addition to any other remedy to which they may be entitled at law or in equity. Any requirements for the securing or posting of any bond with such remedy are hereby waived.

(b) Notwithstanding any other section in this Agreement and without limiting any other remedies the Company may have in law or equity, in the event that the Investors shall have

11

materially breached this Agreement and shall not have cured such breach within 15 calendar days following written notice describing such breach in reasonable detail from the Company, the Director Designee shall, upon the written request of the Board, resign as a member of the Board, such resignation to be effective as of the time the Board has delivered such request to the Director Designee and TFM.

(c) Each party hereto agrees, on behalf of itself and its Affiliates, that any actions, suits or proceedings arising out of or relating to this Agreement or the transactions contemplated hereby will be brought solely and exclusively in the Chancery Court of the State of Delaware, or if such court does not accept jurisdiction then any federal court in the State of Delaware, or, if such courts do not accept jurisdiction then any state or federal court in the State of New York (and the parties agree not to commence any action, suit or proceeding relating thereto except in such courts), and further agrees that service of any process, summons, notice or document by U.S. registered mail to the respective addresses set forth in Section 3.3 will be effective service of process for any such action, suit or proceeding brought against any party in any such court. Each party, on behalf of itself and its Affiliates, irrevocably and unconditionally waives any objection to the laying of venue of any action, suit or proceeding arising out of this Agreement or the transactions contemplated hereby, in the Chancery Court of the State of Delaware or if such court does not accept jurisdiction then the federal courts in the State of Delaware, or, if such courts do not accept jurisdiction then any state or federal court in the State of New York, and hereby further irrevocably and unconditionally waives and agrees not to plead or claim in any such court that any such action, suit or proceeding brought in any such court has been brought in an improper or inconvenient forum.

SECTION 3.2 Entire Agreement. This Agreement contains the entire understanding of the parties with respect to the subject matter hereof and may be amended only by an agreement in writing executed by the parties hereto. No rights under this Agreement shall be deemed waived absent a written waiver by the party granting the waiver.

SECTION 3.3 Notices. All notices, consents, requests, instructions, approvals and other communications provided for herein and all legal process in regard hereto shall be in writing and shall be deemed validly given, made or served, if (a) given by telecopy, when such telecopy is transmitted to the telecopy number set forth below and the appropriate confirmation is received or (b) if given by any other means, when actually received during normal business hours at the address specified in this subsection:

if to the Company:

with a copy to:

12

if to the Investors:

SECTION 3.4 Governing Law. This Agreement and any claim, controversy or dispute arising under or related to this Agreement, the relationship of the parties, and/or the interpretation and enforcement of the rights and duties of the parties shall be governed by and construed and enforced in accordance with the laws of the State of Delaware, without regard to any conflict of laws provisions thereof.

SECTION 3.5 Further Assurances. Each party agrees to take or cause to be taken such further actions, and to execute, deliver and file or cause to be executed, delivered and filed such further documents and instruments, and to obtain such consents, as may be reasonably required or requested by the other parties in order to effectuate fully the purposes, terms and conditions of this Agreement.

SECTION 3.6 Third-Party Beneficiaries. This Agreement shall inure to the benefit of and be binding upon the parties hereto and their respective successors and permitted assigns, and nothing in this Agreement is intended to confer on any person other than the parties hereto or their respective successors and assigns, any rights, remedies, obligations or liabilities under or by reason of this Agreement. The rights and obligations under this Agreement may not be transferred without the consent of the other parties and any transfer in violation of this sentence shall be null and void.

SECTION 3.7 Counterparts; Miscellaneous. This Agreement may be executed and delivered (including by facsimile transmission or .pdf format) in one or more counterparts, each of which shall be deemed an original, but all of which together shall constitute one and the same instrument. The headings used herein are for convenience only and the parties agree that such headings are not to be construed to be part of this Agreement or to be used in determining the meaning or interpretation of this Agreement. Unless the context otherwise requires, whenever used in this Agreement the singular shall include the plural, the plural shall include the singular, and the masculine gender shall include the neuter or feminine gender and vice versa. Except as otherwise expressly provided herein, no failure on the part of any party to exercise, and no delay in exercising, any right, power or remedy hereunder, or otherwise available in law or in equity, shall operate as a waiver thereof, nor shall any single or partial exercise of such right, power or remedy by such party preclude any other or further exercise thereof or the exercise of any other

13

right, power or remedy. If any provision of this Agreement or the application thereof, becomes or is declared by a court of competent jurisdiction to be illegal, void or unenforceable, the remainder of this Agreement will continue in full force and effect so long as the remaining provisions do not fundamentally alter the relations among the parties.

SECTION 3.9 Interpretation. Each of the parties hereto acknowledges that it has been represented by counsel of its choice throughout all negotiations that have preceded the execution of this Agreement, and that it has executed the same with the advice of said counsel. Each party and its counsel cooperated and participated in the drafting and preparation of this Agreement and the documents referred to herein, and any and all drafts relating thereto exchanged among the parties shall be deemed the work product of all of the parties and may not be construed against any party by reason of its drafting or preparation. Accordingly, any rule of law or any legal decision that would require interpretation of any ambiguities in this Agreement against any party that drafted or prepared it is of no application and is hereby expressly waived by each of the parties hereto.

[Remainder of Page Intentionally Left Blank]

14

IN WITNESS WHEREOF, each of the parties hereto has executed this Agreement, or caused the same to be executed by its duly authorized representative as of the date first above written.

[Signature Page to Agreement – Page 1 of 2]

[Signature Page to Agreement – Page 2 of 2]

SCHEDULE A

As of September 28, 2011, the Investors Economically Own, in the aggregate, 9,965,765 shares of Common Stock. The Investors that own such shares and the number of shares that they Economically Own are set forth below.

A-1

SCHEDULE B

FAMILY DOLLAR CONTACT(S):

Kiley F. Rawlins, CFA

(704) 849-7496

krawlins@familydollar.com

Josh Braverman

(704) 814-3447

jbraverman@familydollar.com

TRIAN FUND MANAGEMENT, L.P. CONTACT:

Anne Tarbell

(212) 451-3030

atarbell@trianpartners.com

NOT For Immediate Release

FAMILY DOLLAR APPOINTS EDWARD GARDEN OF TRIAN PARTNERS TO BOARD OF DIRECTORS

MATTHEWS, NC, September 29, 2011 – Family Dollar Stores, Inc. (NYSE: FDO) and Trian Fund Management, L.P. (“Trian Partners”) today announced that Family Dollar Stores, Inc. has appointed Edward P. Garden, Chief Investment Officer and a founding partner of Trian Partners, as a director, effective immediately. With the addition of Mr. Garden, Family Dollar’s Board will be expanded to eleven directors.

“We are firmly committed to enhancing value for all Family Dollar stockholders and have always welcomed open dialogue with our shareholders,” said Howard Levine, Chairman and CEO of Family Dollar. “We are pleased to appoint Ed Garden to the Family Dollar Board and look forward to working closely with him. Ed brings to Family Dollar the perspective of a major stockholder and years of experience investing in and working with consumer related companies. His expertise will be valuable to the Company as we continue to drive growth and further strengthen our business.”

“Family Dollar’s continued strong performance, as evidenced by our recently reported fourth quarter and full-year 2011 results, is a testament to the strength of our strategic plan,” continued Mr. Levine. “We are committed to continuing to provide customers with value and convenience while making impactful investments to improve the shopping experience in our stores and our profitability.”

B-1

Ed Garden commented, “Family Dollar is a great company with great potential. Over the past year, Trian Partners has been engaged in constructive dialogue with Howard Levine and other members of the Family Dollar management team. We share their view that the strategic initiatives Family Dollar has implemented have significantly improved the Company’s operating performance and future financial prospects. I look forward to contributing as a Board member and working closely and constructively with the management team and my fellow directors to help advance our shared goal of enhancing value for all Family Dollar stockholders.”

Edward Garden, 50, is the Chief Investment Officer and a founding partner of Trian Partners. In addition, Mr. Garden is a member of the board of directors of The Wendy’s Company (formerly known as Wendy’s/Arby’s Group, Inc. and prior to that Triarc Companies, Inc. (“Triarc”)). He served as Vice Chairman and a director of Triarc from December 2004 through June 2007 and Executive Vice President from August 2003 until December 2004. Prior thereto, Mr. Garden was a Managing Director of Credit Suisse First Boston.

In connection with the appointment of Mr. Garden to the Family Dollar Board, the Company entered into an agreement with Trian Partners and certain of its affiliates. The complete agreement will be included as an exhibit to the Company’s Current Report on Form 8-K to be filed today with the Securities and Exchange Commission.

Cautionary Statements

Certain statements contained in this press release are “forward-looking statements” that are subject to the safe harbor provisions of the Private Securities Litigation Reform Act of 1995. These forward-looking statements address certain plans, activities or events which the Company expects will or may occur in the future and relate to, among other things, the state of the economy, the Company’s investment and financing plans, net sales, comparable store sales, cost of sales, SG&A expenses, earnings per diluted share, dividends and share repurchases. Various risks, uncertainties and other factors could cause actual results to differ materially from those expressed in any forward-looking statement. Consequently, all of the forward-looking statements made by the Company in this and in other documents or statements are qualified by factors, risks and uncertainties, including, but not limited to, those set forth under the headings titled “Cautionary Statement Regarding Forward-Looking Statements” and “Risk Factors” in the Company’s most recent Annual Report on Form 10-K and subsequent Quarterly Reports on Form 10-Q filed with the Securities and Exchange Commission up to the date of this release.

Readers are cautioned not to place undue reliance on these forward-looking statements, which speak only as of the date of this press release. The Company does not undertake to update or revise these forward-looking statements even if experience or future changes make it clear that projected results expressed or implied in such statements will not be realized, except as may be required by law.

B-2

About Family Dollar Stores, Inc.

For more than 50 years, Family Dollar has been providing value and convenience to customers in easy-to-shop neighborhood locations. Family Dollar’s mix of name brands and quality, private brand merchandise, appeals to shoppers in more than 7,000 stores in rural and urban settings across 44 states. Helping families save on the items they need with everyday low prices creates a strong bond with customers who refer to their neighborhood store as “my Family Dollar.” Headquartered in Matthews, North Carolina, just outside of Charlotte, Family Dollar is a Fortune 300, publicly held company with common stock traded on the New York Stock Exchange under the symbol FDO. For more information, please visit www.familydollar.com.

About Trian Partners

Founded in November 2005, Trian Fund Management, L.P. (“Trian Partners”) is an investment firm whose Principals are Nelson Peltz, Peter May and Ed Garden. Trian Partners employs an operations-centric “constructivist” investment strategy that is based on its Principals’ 35+ year track record of successfully working with management teams and boards of directors to build businesses in a broad range of industries.

# # #

B-3