AGREEMENT

Exhibit 10.1

AGREEMENT

This agreement (this “Agreement”) is made and entered into as of April 10, 2015, by and among Staples, Inc. (the “Company”) and the entities and natural persons listed on Exhibit A hereto and their respective Affiliates and Associates (collectively, “Starboard”) (each of the Company and Starboard, a “Party” to this Agreement, and collectively, the “Parties”).

RECITALS

WHEREAS, Starboard is deemed to beneficially own shares of common stock of the Company (the “Common Stock”) totaling, in the aggregate, 24,481,811 shares, or approximately 3.8% of the Common Stock issued and outstanding on the date hereof;

WHEREAS, on March 4, 2015, Starboard delivered a letter to the Company, giving notice (the “Nomination Notice”) of its intent to nominate four (4) individuals for election to the Company’s board of directors (the “Board”) at the 2015 annual meeting of stockholders of the Company (the “2015 Annual Meeting”); and

WHEREAS, the Company and Starboard have determined to come to an agreement with respect to the addition of an independent director candidate to the Board at the 2015 Annual Meeting; certain matters related to the 2015 Annual Meeting; and certain other matters, all as provided in this Agreement.

NOW, THEREFORE, in consideration of the foregoing premises and the mutual covenants and agreements contained in this Agreement, and for other good and valuable consideration, the receipt and sufficiency of which are acknowledged, the Parties hereto, intending to be legally bound hereby, agree as follows:

1.                                      Board Matters; Board Nomination; Committee Appointment; 2015 Annual Meeting.

(a)                                 Prior to the mailing of its definitive proxy statement for the 2015 Annual Meeting, the Company agrees that the Board and all applicable committees of the Board will take all necessary actions to nominate one of the director candidates previously identified by Starboard (the “New Director”, and collectively with the Company’s other director nominees for the 2015 Annual Meeting, the “2015 Nominees”) for election to the Board at the 2015 Annual Meeting for a term of office to expire at the Company’s next annual meeting of stockholders (the “2016 Annual Meeting”).  The Company agrees that the Board shall confirm to Starboard which director candidate the Board has accepted and approved as the New Director by no later than April 9, 2015.  The Company agrees to publicly announce the selection of the New Director no later than April 10, 2015.

(b)                                 Prior to the nomination of the New Director by the Board in accordance with Section 1(a), the Nominating & Governance Committee of the Board (the “Governance Committee”) shall have reviewed and reasonably approved, in accordance with the Company’s corporate governance guidelines and the Governance Committee’s charter, the qualifications of the New Director to serve as a member of the Board and recommended to the Board that the

Board nominate the New Director for election to the Board at the 2015 Annual Meeting in accordance with Section 1(a).

(c)                                  Upon the execution of this Agreement, Starboard hereby irrevocably withdraws the Nomination Notice and its director nominations in connection with the 2015 Annual Meeting and Starboard will not (i) nominate any person for election at the 2015 Annual Meeting, (ii) submit any proposal for consideration at, or bring any other business before, the 2015 Annual Meeting, directly or indirectly, or (iii) initiate, encourage or participate in any “withhold” or similar campaign with respect to the 2015 Annual Meeting, directly or indirectly, and not permit any of its Affiliates or Associates to do any of the items in this Section 1(c).

(d)                                 From the date hereof to the thirtieth (30th) day prior to the advance notice deadline for making director nominations at the 2016 Annual Meeting, Starboard agrees not to, directly or indirectly, (i) request or otherwise submit any proposal for consideration at, or bring any other business before, any special meeting of the shareholders of the Company or (ii) initiate, encourage or participate in any “consent solicitation” or similar campaign, and not permit any of its Affiliates or Associates to do any of the items in this Section 1(d).

(e)                                  The Company agrees that it will recommend, support and solicit proxies for the election of the New Director in the same manner as for the other 2015 Nominees at the 2015 Annual Meeting.

(f)                                   The Company agrees that if the New Director or any Replacement Director (as defined below) is unable to serve as a director, resigns as a director or is removed as a director prior to the 2016 Annual Meeting, and at such time Starboard beneficially owns in the aggregate at least the lesser of three percent (3.0%) of the Company’s then outstanding Common Stock and 19,214,613 shares of Common Stock (subject to adjustment for stock splits, reclassifications, combinations and similar adjustments), Starboard will be permitted to recommend a substitute person(s) for approval by the Governance Committee to fill the resulting vacancy, which person will (i) be independent of Starboard and (ii) qualify as “independent” pursuant to The NASDAQ Stock Market LLC (“NASDAQ”) listing standards and (iii) have relevant financial and business experience to fill the resulting vacancy. The appointment of any such person to the Board will be subject to the approval of the Governance Committee after exercising its fiduciary duties in good faith, which approval shall not be unreasonably withheld (any such replacement nominee appointed in accordance with the terms of this Section 1(f) will be referred to as herein the “Replacement Director”).  In the event the Governance Committee does not accept a substitute person recommended by Starboard as the Replacement Director, Starboard will have the right to recommend additional substitute person(s) for consideration by the Governance Committee as the Replacement Director, who will also be (i) independent of Starboard, (ii) qualify as “independent” pursuant to NASDAQ listing standards and (iii) have relevant financial and business experience to fill the resulting vacancy, and whose appointment shall be subject to the approval of the Governance Committee after exercising its fiduciary duties in good faith, which approval shall not be unreasonably withheld. Upon the acceptance of a Replacement Director nominee by the Governance Committee, the Board will appoint such Replacement Director to the Board no later than five business days after the Governance Committee recommendation of such Replacement Director.

2

(g)                                  As used in this Agreement, the terms “Affiliate” and “Associate” have the respective meanings set forth in Rule 12b-2 promulgated by the Securities and Exchange Commission under the Securities Exchange Act of 1934, as amended, or the rules or regulations promulgated thereunder (the “Exchange Act”) and include all persons or entities that at any time during the term of this Agreement become Affiliates or Associates of any person or entity referred to in this Agreement.

(h)                                 The Company will use its reasonable best efforts to hold the 2015 Annual Meeting no later than June 30, 2015.

(i)                                     The Company agrees that the New Director shall be considered along with all other Board members for Board committee appointment in connection with the Board’s annual review of committee composition. In any event, the Company agrees that the New Director, including any Replacement Director, as applicable, will be appointed to at least one of the Board’s standing committees.

(j)                                    The Company agrees that if it must cause a director to resign prior to the 2016 Annual Meeting in accordance with Section 5.17 of that certain Agreement and Plan of Merger with Office Depot, Inc., then such director shall not be the New Director.

(k)                                 At the 2015 Annual Meeting, Starboard agrees to appear in person or by proxy and vote all shares of Common Stock of the Company beneficially owned by it and its Affiliates in favor of the election of each of the Company’s nominees for election to the Board and for each other proposal to come before the 2015 Annual Meeting in accordance with the Board’s recommendation, unless solely as relates to any proposal other than the election of directors, Institutional Shareholder Services Inc. and Glass Lewis & Co., LLC recommends otherwise.

2.                                      Representations and Warranties of the Company.

The Company represents and warrants to Starboard that (a) the Company has the corporate power and authority to execute this Agreement and to bind it thereto, (b) this Agreement has been duly and validly authorized, executed and delivered by the Company, constitutes a valid and binding obligation and agreement of the Company, and is enforceable against the Company in accordance with its terms, except as enforcement thereof may be limited by applicable bankruptcy, insolvency, reorganization, moratorium, fraudulent conveyance or similar laws generally affecting the rights of creditors and subject to general equity principles, and (c) the execution, delivery and performance of this Agreement by the Company does not and will not violate or conflict with (i) any law, rule, regulation, order, judgment or decree applicable to the Company or (ii) result in any breach or violation of or constitute a default (or an event which with notice or lapse of time or both could constitute such a breach, violation or default) under or pursuant to, or result in the loss of a material benefit under, or give any right of termination, amendment, acceleration or cancellation of, any organizational document, agreement, contract, commitment, understanding or arrangement to which the Company is a party or by which it is bound.

3

3.                                      Representations and Warranties of Starboard.

Starboard represents and warrants to the Company that (a) the authorized signatory of Starboard set forth on the signature page hereto has the power and authority to execute this Agreement and any other documents or agreements to be entered into in connection with this Agreement and to bind it thereto, (b) this Agreement has been duly authorized, executed and delivered by Starboard, and is a valid and binding obligation of Starboard, enforceable against Starboard in accordance with its terms, except as enforcement thereof may be limited by applicable bankruptcy, insolvency, reorganization, moratorium, fraudulent conveyance or similar laws generally affecting the rights of creditors and subject to general equity principles, (c) the execution of this Agreement, the consummation of any of the transactions contemplated hereby, and the fulfillment of the terms hereof, in each case in accordance with the terms hereof, will not conflict with, or result in a breach or violation of the organizational documents of Starboard as currently in effect, (d) the execution, delivery and performance of this Agreement by Starboard does not and will not violate or conflict with (i) any law, rule, regulation, order, judgment or decree applicable to Starboard or (ii) result in any breach or violation of or constitute a default (or an event which with notice or lapse of time or both could constitute such a breach, violation or default) under or pursuant to, or result in the loss of a material benefit under, or give any right of termination, amendment, acceleration or cancellation of, any organizational document, agreement, contract, commitment, understanding or arrangement to which such member is a party or by which it is bound.

4.                                      Press Release; Non-Disparagement.

(a)                                 The Company will publish a press release (the “Press Release”) announcing certain terms of this Agreement, substantially in the form attached hereto as Exhibit B, together with the public announcement of the selection of the New Director in accordance with Section 1(a).  Prior to the publication of the Press Release, neither the Company nor Starboard will publish or make any press release or public announcement regarding this Agreement without the prior written consent of the other Party.  Until the 2015 Annual Meeting, neither the Company nor Starboard will knowingly make any public announcement or statement that is inconsistent with or contrary to the statements made in the Press Release, except as required by law or the rules of any stock exchange or with the prior written consent of the other Party.

(b)                                 Each of the Parties covenants and agrees that, from the date hereof and for so long as the New Director or any Replacement Director is serving as a member of the Board, neither it nor any of its respective agents, subsidiaries, Affiliates, successors, assigns, officers, key employees or directors, shall in any way disparage, call into disrepute, or otherwise defame or slander the other Parties or such other Parties’ subsidiaries, Affiliates, successors, assigns, officers (including any current officer of a Party or a Parties’ subsidiaries who no longer serves in such capacity following the execution of this Agreement), directors (including any current director of a Party or a Parties’ subsidiaries who no longer serves in such capacity following the execution of this Agreement), employees, shareholders, agents, attorneys or representatives, or any of their products or services or past actions taken relating to the Nomination Notice or the attempts by Starboard to influence the composition of the Board, in any manner that would damage the business or reputation of such other Parties, their products or services or their

4

subsidiaries, Affiliates, successors, assigns, officers (or former officers), directors (or former directors), employees, shareholders, agents, attorneys or representatives.

5.                                      Specific Performance.

Each of Starboard, on the one hand, and the Company, on the other hand, acknowledges and agrees that irreparable injury to the other party hereto 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 and that such injury would not be adequately compensable by the remedies available at law (including the payment of money damages).  It is accordingly agreed that Starboard, on the one hand, and the Company, on the other hand (the “Moving Party”), will each be entitled to specific enforcement of, and injunctive relief to prevent any violation of, the terms hereof, and the other party hereto will not take action, directly or indirectly, in opposition to the Moving Party seeking such relief on the grounds that any other remedy or relief is available at law or in equity.  This Section 5 is not the exclusive remedy for any violation of this Agreement. In the event a Party institutes any legal action to enforce such Party’s rights, or recover damage for breach of this Agreement, the prevailing Party or Parties in such action shall be entitled to recover from the other Party or Parties all out-of-pocket costs and expenses, including but not limited to reasonable attorney’s fees, court costs, witness fees, disbursements and any other expenses of litigation or negotiations incurred by such prevailing Party or Parties.

6.                                      Expenses.

The Company has agreed to reimburse Starboard for its reasonable, documented out-of-pocket travel and legal fees, costs and expenses actually incurred by Starboard in connection with, relating to or resulting from Starboard’s negotiation, settlement and execution of this Agreement; provided however, in no event shall the Company reimburse Starboard for an amount in excess of $25,000, in the aggregate.

7.                                      Severability.

If any term, provision, covenant or restriction of this Agreement is held by a court of competent jurisdiction to be invalid, void or unenforceable, the remainder of the terms, provisions, covenants and restrictions of this Agreement will remain in full force and effect and will in no way be affected, impaired or invalidated.  It is hereby stipulated and declared to be the intention of the Parties that the Parties would have executed the remaining terms, provisions, covenants and restrictions without including any of such which may be hereafter declared invalid, void or unenforceable.  In addition, the Parties agree to use their respective best efforts to agree upon and substitute a valid and enforceable term, provision, covenant or restriction for any of such that is held invalid, void or enforceable by a court of competent jurisdiction.

8.                                      Notices.

Any notices, consents, determinations, waivers or other communications required or permitted to be given under the terms of this Agreement must be in writing and will be deemed to have been delivered:  (i) upon receipt, when delivered personally, (ii) upon receipt, when sent by facsimile (provided confirmation of transmission is mechanically or electronically generated and kept on file by the sending party), or (iii) one business day after deposit with a nationally

5

recognized overnight delivery service, in each case properly addressed to the party to receive the same.  The addresses and facsimile numbers for such communications will be:

6

9.                                      Applicable Law.

This Agreement will be governed by and construed and enforced in accordance with the laws of the State of Delaware without reference to the conflict of laws principles thereof.  Each of the Parties hereto irrevocably agrees that any legal action or proceeding with respect to this Agreement and the rights and obligations arising hereunder, or for recognition and enforcement of any judgment in respect of this Agreement and the rights and obligations arising hereunder brought by the other party hereto or its successors or assigns, will be brought and determined exclusively in the Delaware Court of Chancery and any state appellate court therefrom within the State of Delaware (or, if the Delaware Court of Chancery declines to accept jurisdiction over a particular matter, any state or federal court within the State of Delaware).  Each of the Parties hereto hereby irrevocably submits, with regard to any such action or proceeding for itself and in respect of its property, generally and unconditionally, to the personal jurisdiction of the aforesaid courts and agrees that it will not bring any action relating to this Agreement in any court other than the aforesaid courts.  Each of the Parties hereto hereby irrevocably waives, and agrees not to assert in any action or proceeding with respect to this Agreement, (i) any claim that it is not personally subject to the jurisdiction of the above-named courts for any reason, (ii) any claim that it or its property is exempt or immune from jurisdiction of any such court or from any legal process commenced in such courts (whether through service of notice, attachment prior to judgment, attachment in aid of execution of judgment, execution of judgment or otherwise), and (iii) to the fullest extent permitted by applicable legal requirements, any claim that (A) the suit, action or proceeding in such court is brought in an inconvenient forum, (B) the venue of such suit, action or proceeding is improper, or (C) this Agreement, or the subject matter hereof, may not be enforced in or by such courts.

10.                               Counterparts.

This Agreement may be executed in two or more counterparts, each of which will be considered one and the same agreement and shall become effective when counterparts have been signed by each of the Parties and delivered to the other Party (including by means of electronic delivery or facsimile).

11.                               Entire Agreement; Amendment and Waiver; Successors and Assigns; Third Party Beneficiaries.

This Agreement contains the entire understanding of the Parties hereto with respect to its subject matter.  There are no restrictions, agreements, promises, representations, warranties,

7

covenants or undertakings between the Parties other than those expressly set forth herein.  No modifications of this Agreement may be made except in writing signed by an authorized representative of each the Company and Starboard, except that the signature of an authorized representative of the Company will not be required to permit an Affiliate of Starboard to agree to be listed on Exhibit A and be bound by the terms and conditions of this Agreement.  No failure on the part of any party to exercise, and no delay in exercising, any right, power or remedy hereunder shall operate as a waiver thereof, nor will 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 right, power or remedy.  All remedies hereunder are cumulative and are not exclusive of any other remedies provided by law.  The terms and conditions of this Agreement will be binding upon, inure to the benefit of, and be enforceable by the Parties hereto and their respective successors, heirs, executors, legal representatives, and permitted assigns.  No party will assign this Agreement or any rights or obligations hereunder without, with respect to any member of Starboard, the prior written consent of the Company, and with respect to the Company, the prior written consent of Starboard.  This Agreement is solely for the benefit of the Parties and is not enforceable by any other persons.

 [The remainder of this page intentionally left blank]

8

IN WITNESS WHEREOF, this Agreement has been duly executed and delivered by the duly authorized signatories of the Parties as of the date hereof.

[Signature Page to Agreement]

[Signature Page to Agreement]

EXHIBIT A

Starboard Value and Opportunity Master Fund Ltd

Starboard Value and Opportunity S LLC

Starboard Value and Opportunity C LP

Starboard Leaders Golf LLC

Starboard Leaders Fund LP

Starboard Value R LP

Starboard Value R GP LLC

Starboard Value A LP

Starboard Value A GP LLC

Starboard Value LP

Starboard Value GP LLC

Starboard Principal Co LP

Starboard Principal Co GP LLC

Jeffrey C. Smith

Mark R. Mitchell

Peter A. Feld

EXHIBIT B

PRESS RELEASE