Agreement between Scott Galloway and RedEnvelope, Inc. dated July 13, 2005

Exhibit 10.1

AGREEMENT

     This Agreement (the “Agreement”) is entered into this 13th day of July, 2005, by and between RedEnvelope, Inc., a Delaware corporation (“RedEnvelope” or the “Company”), on the one hand, and Scott Galloway, on behalf of himself, R. Ian Chaplin, Martin McClanan, Michael L. Meyer, Firebrand Partners, LLC, a Delaware limited liability company, Glenn J. Krevlin, Krevlin Advisors, LLC, a Delaware limited liability company, GJK Capital Management, LLC, a Delaware limited liability company, Glenhill Capital LP, a Delaware limited partnership, Glenhill Capital Overseas GP, Ltd., a Cayman Islands exempted company and Glenhill Capital Overseas Master Fund, L.P., a Cayman Islands exempted limited partnership (collectively, the “Galloway/Krevlin Group”), on the other hand.

RECITALS

     A. On May 12, 2005, Scott Galloway filed, on behalf of himself, R. Ian Chaplin, Martin McClanan and Michael L. Meyer (the “Galloway Group”) Amendment No. 3 to the Schedule 13D initially filed by and on behalf of the Galloway Group on June 30, 2004 (the “Schedule 13D”), indicating that the Galloway Group may consider, among other alternatives, soliciting authority from RedEnvelope stockholders to elect an alternative slate of nominees for election as RedEnvelope directors at RedEnvelope’s upcoming 2005 annual meeting of stockholders (the “2005 Stockholder Meeting”).

     B. In a letter dated May 27, 2005, Mr. Galloway provided notice to RedEnvelope, pursuant to Section 2.5 of the RedEnvelope Bylaws, to nominate himself, Robert M. Perkowitz, John Pound and Gregory Shove (the “Galloway Candidates”) for election as RedEnvelope directors at the 2005 Stockholder Meeting.

     C. On May 31, 2005, Mr. Galloway filed, on behalf of the Galloway/Krevlin Group, Amendment No. 4 to the Schedule 13D, which included additional members to the group on whose behalf the Schedule 13D was filed and which stated that Mr. Galloway had expressed to the RedEnvelope Board of Directors (the “Board”) his hope that the RedEnvelope nominating committee would review and select the Galloway Candidates as Board nominees to be presented to the RedEnvelope stockholders. Amendment No. 4 to the Schedule 13D then stated the Galloway/Krevlin Group’s intention to consider a number of alternatives in the event that it is unsuccessful in convincing the RedEnvelope nominating committee or Board to accept the Galloway Candidates or effect other governance changes, including soliciting authority from the RedEnvelope stockholders to elect the Galloway Candidates to the RedEnvelope Board at the 2005 Stockholder Meeting.

     D. On June 14, 2005 and June 17, 2005, the Galloway/Krevlin Group filed Amendments No. 5 and No. 6, respectively, to the Schedule 13D.

     E. In a letter dated July 5, 2005, Mr. Galloway made written demand pursuant to Section 220 of the Delaware General Corporation Law to inspect certain records and lists of RedEnvelope stockholders and certain other documents (the “Demand Letter”).

     F. Following a rigorous review process that involved careful consideration and evaluation of, and interviews with, numerous prospective director candidates over the course of the past year, the RedEnvelope nominating committee has identified three new director candidates, willing and able to serve on the Board, that the Board (including its nominating committee) deems to be qualified and suitable to serve on the Board, including one candidate who initially was recommended to the Board’s nominating committee by the Galloway/Krevlin Group (and who is one of the Galloway Candidates) and two other candidates acceptable to the Galloway/Krevlin Group, and that the Board will present to the RedEnvelope stockholders such three candidates as nominees for election to the Board at the 2005 Stockholder Meeting.

     G. The parties desire to set forth certain covenants and agreements relating to the matters set forth above, and to resolve amicably their current disputes regarding the individuals to be presented to the RedEnvelope stockholders as nominees for election to the Board without the burden, distraction or expense of a proxy contest.

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

AGREEMENT

     1. Covenants of RedEnvelope. RedEnvelope covenants and agrees that, in reliance on the covenants and agreements of Scott Galloway and the Galloway/Krevlin Group set forth in Section 2 below:

     (a) the Board (including its nominating committee) will nominate, present and recommend for election to the RedEnvelope stockholders at the 2005 Stockholder Meeting a slate of up to nine (9) director candidates that includes Greggory Hammond, Brett Hendrickson and John Pound (these three persons herein referred to as the “New Candidates”), subject to any decision one or more of such individuals may make not to stand for election (although RedEnvelope currently is not aware of any such decision not to so stand);

     (b) its Board will appoint at least one of the New Candidates, if elected, to serve on its Nominating/Corporate Governance Committee, which committee has expanded its charter to include corporate governance functions and that such committee is charged with, among other things, the responsibility to, at least annually, review the performance of the Company’s Chief Executive Officer; and

2

     (c) on or before July 15, 2005, it will issue or cause to be issued a press release announcing the slate of directors, including the New Candidates, that the Board intends to present to the RedEnvelope stockholders for election at the 2005 Stockholder Meeting. RedEnvelope shall give the Galloway/Krevlin Group a reasonable opportunity to review and comment on this press release before its issuance.

     2. Covenants of Scott Galloway and the Galloway/Krevlin Group. Scott Galloway, on behalf of himself and the other members of the Galloway/Krevlin Group, covenants and agrees that, in reliance on the covenants and agreements of RedEnvelope set forth in Section 1 above:

     (a) they will not solicit authority, directly or indirectly, from any RedEnvelope stockholder to elect or vote for any candidate or candidates for election to the Board at the 2005 Stockholder Meeting other than the candidates nominated by the Board and its nominating committee (the “Board Nominees”) or otherwise present for consideration to any RedEnvelope stockholder in connection with the 2005 Stockholder Meeting any candidates other than the Board Nominees, nor will they engage in any campaign or efforts to have votes withheld from or otherwise discredit any of the Board Nominees in connection with the 2005 Stockholder Meeting or cause any other party to do, or assist any other party in doing, any of the foregoing;

     (b) on or before July 13, 2005, they will amend or cause to be amended the Schedule 13D to indicate that they no longer intend to solicit authority to elect candidates to the Board at the 2005 Stockholder Meeting in light of reaching an agreement with the Company to nominate three mutually acceptable candidates (who shall not be named in such amendment) for election to the Company’s Board at such meeting, one of whom will be appointed to sit on the Company’s Nominating/Corporate Governance Committee, which is charged with, among other things, at least annually reviewing the performance of the Company’s Chief Executive Officer. (The Galloway/Krevlin Group shall give RedEnvelope a reasonable opportunity to review and comment on this amendment before it is filed.); and

     (c) immediately following the Company’s public announcement of the New Candidates in accordance with this Agreement, Galloway shall rescind notice of his intention to nominate the Galloway Candidates at the 2005 Stockholder Meeting and agree that the Galloway/Krevlin Group will not propose or seek to propose any director candidates or any other matters to come before the stockholders at the 2005 Stockholder Meeting. For purposes of clarity, the demand to inspect certain records and lists of RedEnvelope stockholders and certain other documents as set forth in the Demand Letter is hereby rescinded.

     3. No Assurances. No party to this Agreement provides any quarantees or assurances that each of the Board Nominees will be elected by the stockholders, will

3

agree to serve, or will actually serve, a full term if elected and no party makes any representation or warranty as to the fitness of any Board Nominee to serve on the Board.

     4. General.

          (a) RedEnvelope represents that the individual set forth below as signatory to this Agreement for RedEnvelope has the authority to execute this Agreement on behalf of RedEnvelope and to bind RedEnvelope to the terms hereof. Scott Galloway represents that the he has the authority to execute the Agreement on behalf of himself and the other members of the Galloway/Krevlin Group to bind each of them to the terms hereof.

          (b) This Agreement shall be governed by the laws of the State of Delaware, without regard to the conflicts of law provisions thereof.

          (c) This Agreement may be executed in two or more counterparts, each of which shall be deemed an original and all of which together shall constitute one instrument.

          (d) The terms and conditions of this Agreement shall inure to the benefit of and be binding upon the respective successors and assigns of the Parties. Nothing in this Agreement, express or implied, is intended to confer upon any party other than the parties hereto or their respective successors and assigns any rights, remedies, obligations or liabilities under or by reason of this Agreement, except as expressly provided in this Agreement.

          (e) If one or more provisions of this Agreement are held to be unenforceable under applicable law, the parties agree to renegotiate such provision(s) in good faith so as to become enforceable while hewing as closely as possible to the original intent. In the event that the parties cannot reach a mutually agreeable and enforceable replacement for such provision(s), then (i) such provision shall be excluded from this Agreement, (ii) the balance of this Agreement shall be interpreted as if such provision were so excluded and (iii) the balance of this Agreement shall remain enforceable in accordance with its terms.

          (f) Each party acknowledges that its breach of this Agreement would cause irreparable injury to the other for which monetary damages would not be an adequate remedy. Accordingly, a party will be entitled to injunctions and other equitable remedies in the event of such a breach by the other Party (or any of its members).

          (g) This Agreement constitutes the entire agreement between the parties hereto pertaining to the subject matter hereof, and any and all other written or oral agreements existing between the parties with respect to the subject matter hereof are expressly canceled.

4

     In Witness Whereof, the Parties have caused this Agreement to be executed and delivered by themselves or their duly authorized officer or attorney-in-fact as of the date first set forth above.

5