Exhibit 10.31

THRESHOLD PHARMACEUTICALS, INC.

CHANGE OF CONTROL SEVERANCE AGREEMENT

The Change of Control Severance Agreement (the “Agreement”) is made and entered into effective as of November 3, 2006 (the “Effective Date”), by and between Michael K. Brawer (the “Employee”) and Threshold Pharmaceuticals, Inc., a Delaware corporation (the “Company”). Certain capitalized terms used in this Agreement are defined in Section 1 below.

RECITALS

A. It is expected that the Company from time to time will consider the possibility of a Change of Control. The Board of Directors of the Company (the “Board”) recognizes that such consideration can be a distraction to the Employee and can cause the Employee to consider alternative employment opportunities.

B. The Board believes that it is in the best interests of the Company and its stockholders to provide the Employee with an incentive to continue Employee’s employment and to maximize the value of the Company upon a Change of Control for the benefit of its stockholders.

C. In order to provide the Employee with enhanced financial security and sufficient encouragement to remain with the Company notwithstanding the possibility of a Change of Control, the Board believes that it is imperative to provide the Employee with certain severance benefits upon the Employee’s termination of employment following a Change of Control.

AGREEMENT

In consideration of the mutual covenants herein contained and the continued employment of Employee by the Company, the parties agree as follows:

1. Definition of Terms. The following terms referred to in this Agreement shall have the following meanings:

(a) Cause. “Cause” shall mean (i) Employee’s gross negligence or willful failure substantially to perform his or her duties and responsibilities to the Company or deliberate violation of a Company policy; (ii) Employee’s commission of any act of fraud, embezzlement, dishonesty or any other willful misconduct that has caused or is reasonably expected to result in material injury to the Company; (iii) unauthorized use or disclosure by Employee of any proprietary information or trade secrets of the Company or any other party to whom the Employee owes an obligation of nondisclosure as a result of his or her relationship with the Company; or (iv) Employee’s willful breach of any of his or her obligations under any written agreement or covenant with the Company. The determination as to whether a Employee is being terminated for Cause shall be made in good faith by the Company and shall be final and binding on the Employee.

1

(b) Change of Control. “Change of Control” shall mean the occurrence of any of the following events:

(i) the approval by stockholders of the Company of 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) more than 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;

(ii) the approval by the stockholders of the Company of a plan of complete liquidation of the Company or an agreement for the sale or disposition by the Company of all or substantially all of the Company’s assets; or

(iii) any “person” (as such term is used in Sections 13(d) and 14(d) of the Securities Exchange Act of 1934, as amended) becoming the “beneficial owner” (as defined in Rule 13d-3 under said Act), directly or indirectly, of securities of the Company representing 50% or more of the total voting power represented by the Company’s then outstanding voting securities.

(c) Involuntary Termination. “Involuntary Termination” shall mean (i) without the Employee’s express written consent, a significant reduction of the Employee’s duties, position or responsibilities relative to the Employee’s duties, position or responsibilities in effect immediately prior to such reduction, or the removal of the Employee from such position, duties and responsibilities, unless the Employee is provided with comparable or greater duties, position and responsibilities; (ii) without the Employee’s express written consent, a substantial reduction, without good business reasons, of the facilities and perquisites (including office space and location) available to the Employee immediately prior to such reduction; (iii) without the Employee’s express written consent, a reduction by the Company of the Employee’s base salary as in effect immediately prior to such reduction; (iv) without the Employee’s express written consent, a material reduction by the Company in the kind or level of employee benefits to which the Employee is entitled immediately prior to such reduction, with the result that the Employee’s overall benefits package is significantly reduced; (v) without the Employee’s express written consent, the imposition of a requirement for the relocation of the Employee to a facility or a location more than fifty (50) miles from the Employee’s current work location; (vi) any purported termination of the Employee’s employment by the Company which is not effected for Cause or for which the grounds relied upon are not valid; or (vii) the failure of the Company to obtain the assumption of this Agreement by any successors contemplated in Section 6 below.

(d) Termination Date. “Termination Date” shall mean the effective date of any notice of termination delivered by one party to the other hereunder.

2. Term of Agreement. Other than Section 4(b) of this Agreement which shall survive indefinitely until all obligations under such Section have been satisfied, this Agreement shall terminate upon the earlier of (i) two (2) years after a Change of Control, or (ii) the date that all obligations of the parties hereto under this Agreement have been satisfied.

2

3. At-Will Employment. The Company and the Employee acknowledge that the Employee’s employment is and shall continue to be at-will, as defined under applicable law. If the Employee’s employment terminates for any reason, the Employee shall not be entitled to any payments, benefits, damages, awards or compensation other than as provided by this Agreement, or as may otherwise be established under the Company’s then existing employee benefit plans or policies at the time of termination.

4. Severance Benefits.

(a) Termination Following a Change of Control. If the Employee’s employment with the Company terminates as a result of an Involuntary Termination at any time within eighteen (18) months after a Change of Control, and the Employee signs the release of claims pursuant to Section 7 hereto, Employee shall be entitled to the following severance benefits:

(1) Twelve months of Employee’s base salary and any applicable allowances as in effect as of the date of the termination or, if greater, as in effect in the year in which the Change of Control occurs, less applicable withholding, payable in a lump sum within thirty (30) days of the Involuntary Termination;

(2) all stock options or other awards granted by the Company to the Employee prior to the Change of Control shall accelerate and become vested under the applicable option agreements to the extent such stock options or other awards are outstanding and unexercisable at the time of such termination and all stock subject to a right of repurchase by the Company (or its successor) that was purchased prior to the Change of Control shall have such right of repurchase lapse;

(3) the Employee shall be permitted to exercise all vested (including shares that vest as a result of this Agreement) stock options or other awards granted by the Company to the Employee prior to the Change of Control for a period of two (2) years following the Termination Date; and

(4) the same level of Company-paid health (i.e., medical, vision and dental) coverage and benefits for such coverage as in effect for the Employee (and any eligible dependents) on the day immediately preceding the Employee’s Termination Date; provided, however, that (i) the Employee constitutes a qualified beneficiary, as defined in Section 4980B(g)(1) of the Internal Revenue Code of 1986, as amended; and (ii) Employee elects continuation coverage pursuant to the Consolidated Omnibus Budget Reconciliation Act of 1985, as amended (“COBRA”), within the time period prescribed pursuant to COBRA. The Company shall continue to provide Employee with such Company-paid coverage until the earlier of (i) the date Employee (and his/her eligible dependents) is no longer eligible to receive continuation coverage pursuant to COBRA, or (ii) twelve (12) months from the Termination Date.

(b) Termination Apart from a Change of Control. If (but without duplication with the provisions set forth above in subsection 4(a)(1)) the Employee’s employment with the Company terminates as a result of an Involuntary Termination, the Employee shall be entitled to severance benefits in the form of twelve (12) months of Employee’s base salary as in effect as of the date of termination, less applicable withholding, payable in a lump sum within thirty (30) days of the Involuntary Termination.

3

(c) Accrued Wages and Vacation, Expenses. Without regard to the reason for, or the timing of, Employee’s termination of employment: (i) the Company shall pay the Employee any unpaid base salary due for periods prior to the Termination Date; (ii) the Company shall pay the Employee all of the Employee’s accrued and unused vacation through the Termination Date; and (iii) following submission of proper expense reports by the Employee, the Company shall reimburse the-Employee for all expenses reasonably and necessarily incurred by the Employee in connection with the business of the Company prior to the Termination Date. These payments shall be made promptly upon termination and within the period of time mandated by law.

5. Limitation on Payments. In the event that the severance and other benefits provided for in this Agreement or otherwise payable to the Employee (i) constitute “parachute payments” within the meaning of Section 280G of the Code, and (ii) would be subject to the excise tax imposed by Section 4999 of the Code (the “Excise Tax”), then Employee’s benefits under this Agreement shall be either

(a) delivered in full, or

(b) delivered as to such lesser extent which would result in no portion of such benefits being subject to the Excise Tax,

whichever of the foregoing amounts, taking into account the applicable federal, state and local income taxes and the Excise Tax, results in the receipt by Employee on an after-tax basis, of the greatest amount of benefits, notwithstanding that all or some portion of such benefits may be taxable under Section 4999 of the Code.

Unless the Company and the Employee otherwise agree in writing, any determination required under this Section shall be made in- writing by the Company’s independent public accountants (the “Accountants”), whose determination shall be conclusive and binding upon the Employee and the Company for all purposes. For purposes of making the calculations required by this Section, the Accountants may make reasonable assumptions and approximations concerning applicable taxes and may rely on reasonable, good faith interpretations concerning the application of Section 280G and 4999 of the Code. The Company and the Employee shall furnish to the Accountants such information and documents as the Accountants may reasonably request in order to make a determination under this Section. The Company shall bear all costs the Accountants may reasonably incur in connection with any calculations contemplated by this Section.

6. Successors.

(a) Company’s Successors. Any successor to the Company (whether direct or indirect and whether by purchase, lease, merger, consolidation, liquidation or otherwise) to all or substantially all of the Company’s business and/or assets shall assume the Company’s obligations under this Agreement and agree expressly to perform the Company’s obligations under this Agreement in the same manner and to the same extent as the Company would be

4

required to perform such obligations in the absence of a succession. For all purposes under this Agreement, the term “Company” shall include any successor to the Company’s business and/or assets which executes and delivers the assumption agreement described in this subsection (a) or which becomes bound by the terms of this Agreement by operation of law.

(b) Employee’s Successors. Without the written consent of the Company, Employee shall not assign or transfer this Agreement or any right or obligation under this Agreement to any other person or entity. Notwithstanding the foregoing, the terms of this Agreement and all rights of Employee hereunder shall inure to the benefit of, and be enforceable by, Employee’s personal or legal representatives, executors, administrators, successors, heirs, distributees, devisees and legatees.

7. Execution of Release Agreement upon Termination. As a condition of entering into this Agreement and receiving the benefits under Section 4, the Employee agrees to execute and not revoke a general release of claims upon the termination of employment with the Company.

8. Notices.

(a) General. Notices and all other communications contemplated by this Agreement shall be in writing and shall be deemed to have been duly given when personally delivered or when mailed by U.S. registered or certified mail, return receipt requested and postage prepaid. In the case of the Employee, mailed notices shall be addressed to Employee at the home address which Employee most recently communicated to the Company in writing. In the case of the Company, mailed notices shall be addressed to its corporate headquarters, and all notices shall be directed to the attention of its Chief Executive Officer.

(b) Notice of Termination. Any termination by the Company for Cause or by the Employee as a result of a voluntary resignation shall be communicated by a notice of termination to the other party hereto given in accordance with this Section. Such notice shall indicate the specific termination provision in this Agreement relied upon, shall set forth in reasonable detail the facts and circumstances claimed to provide a basis for termination under the provision so indicated, and shall specify the Termination Date (which shall be not more than 30 days after the giving of such notice). The failure by the Employee to provide the notice or to include in the notice any fact or circumstance which contributes to a showing of Involuntary Termination shall not waive any right of the Employee hereunder or preclude the Employee from asserting such fact or circumstance in enforcing his rights hereunder.

9. Arbitration.

(a) Any dispute or controversy arising out of, relating to, or in connection with this Agreement, or the interpretation, validity, construction, performance, breach, or termination thereof, shall be settled by binding arbitration to be held in Santa Clara, California, in accordance with the National Rules for the Resolution of Employment Disputes then in effect of the American Arbitration Association (the “Rules”). The arbitrator may grant injunctions or other relief in such dispute or controversy. The decision of the arbitrator shall be final, conclusive and binding on the parties to the arbitration. Judgment may be entered on the arbitrator’s decision in any court having jurisdiction. The arbitrator may require one party to pay the costs and attorney fees of the prevailing party.

5

(b) The arbitrator(s) shall apply California law to the merits of any dispute or claim, without reference to conflicts of law rules. The arbitration proceedings shall be governed by federal arbitration law and by the Rules, without reference to state arbitration law. Employee hereby consents to the personal jurisdiction of the state and federal courts located in California for any action or proceeding arising from or relating to this Agreement or relating to any arbitration in which the parties are participants.

(c) Employee understands that nothing in this Section modifies Employee’s at-will employment status. Either Employee or the Company can terminate the employment relationship at any time, with or without Cause.

(d) EMPLOYEE HAS READ AND UNDERSTANDS THIS SECTION, WHICH DISCUSSES ARBITRATION. EMPLOYEE UNDERSTANDS THAT SUBMITTING ANY CLAIMS ARISING OUT OF, RELATING TO, OR IN CONNECTION WITH THIS AGREEMENT, OR THE INTERPRETATION, VALIDITY, CONSTRUCTION, PERFORMANCE, BREACH OR TERMINATION THEREOF TO BINDING ARBITRATION, CONSTITUTES A WAIVER OF EMPLOYEE’S RIGHT TO A JURY TRIAL AND RELATES TO THE RESOLUTION OF ALL DISPUTES RELATING TO ALL ASPECTS OF THE EMPLOYER/EMPLOYEE RELATIONSHIP, INCLUDING BUT NOT LIMITED TO, THE FOLLOWING CLAIMS:

(i) ANY AND ALL CLAIMS FOR WRONGFUL DISCHARGE OF EMPLOYMENT; BREACH OF CONTRACT, BOTH EXPRESS AND IMPLIED; BREACH OF THE COVENANT OF GOOD FAITH AND FAIR DEALING, BOTH EXPRESS AND IMPLIED; NEGLIGENT OR INTENTIONAL INFLICTION OF EMOTIONAL DISTRESS; NEGLIGENT OR INTENTIONAL MISREPRESENTATION; NEGLIGENT OR INTENTIONAL INTERFERENCE WITH CONTRACT OR PROSPECTIVE ECONOMIC ADVANTAGE; AND DEFAMATION.

(ii) ANY AND ALL CLAIMS FOR VIOLATION OF ANY FEDERAL STATE OR MUNICIPAL STATUTE, INCLUDING, BUT NOT LIMITED TO, TITLE VII OF THE CIVIL RIGHTS ACT OF 1964, THE CIVIL RIGHTS ACT OF 1991, 1 AGE DISCRIMINATION IN EMPLOYMENT ACT OF 1967, THE AMERICANS WITH DISABILITIES ACT OF 1990, THE FAIR LABOR STANDARDS ACT, THE CALIFORNIA FAIR EMPLOYMENT AND HOUSING ACT, AND LABOR CODE SECTION 20 1, et seq;

(iii) ANY AND ALL CLAIMS ARISING OUT OF ANY OTHER LAWS AND REGULATIONS RELATING TO EMPLOYMENT OR EMPLOYMENT DISCRIMINATION.

10. Miscellaneous Provisions.

(a) Effect of Statutory Benefits. To the extent that any severance benefits are required to be paid to the Employee upon termination of employment with the Company as a result of any requirement of law or any governmental entity in any applicable jurisdiction, the aggregate amount of severance benefits payable pursuant to Section 4 hereof shall be reduced by such amount.

6

(b) No Duty to Mitigate. The Employee shall not be required to mitigate the amount of any payment contemplated by this Agreement, nor shall any such payment be reduced by any earnings that the Employee may receive from any other source.

(c) Waiver. No provision of this Agreement may be modified, waived or discharged unless the modification, waiver or discharge is agreed to in writing and signed by the Employee and by an authorized officer of the Company (other than the Employee). No waiver by either party of any breach of, or of compliance with, any condition or provision of this Agreement by the other party shall be considered a waiver of any other condition or provision or of the same condition or provision at another time.

(d) Integration. This Agreement and any outstanding stock option agreements and any restricted stock purchase agreements referenced herein represent the entire agreement and understanding between the parties as to the subject matter herein and supersede all prior or contemporaneous agreements, whether written or oral, with respect to this Agreement and any stock option agreement or any restricted stock purchase agreement, provided, that, for clarification purposes, this agreement shall not affect any agreements between the Company and Employee regarding intellectual property matters or confidential information of the Company.

(e) Choice of Law. The validity, interpretation, construction and performance of this Agreement shall be governed by the internal substantive laws, but not the conflicts of law rules, of the State of California.

(f) Severability. The invalidity or unenforceability of any provision or provisions of this Agreement shall not affect the validity or enforceability of any other provision hereof, which shall remain in full force and effect.

(g) Employment Taxes. All payments made pursuant to this Agreement shall be subject to withholding of applicable income and employment taxes.

(h) Counterparts. This Agreement may be executed in counterparts, each of which shall be deemed an original, but all of which together will constitute one and the same instrument.

7

IN WITNESS WHEREOF, each of the parties has executed this Agreement, in the case of the Company by its duly authorized officer, as of the day and year first above written.

8