Page 1

EXHIBIT 10.20

AMENDED AND RESTATED

REPLACES LETTER DATED OCTOBER 1, 2003

December 23, 2003

Via Hand Delivery

Kenneth Klein

Dear Ken:

This letter, upon your signature, will be the agreement (this “Agreement”) between you and Mercury Interactive Corporation (“Mercury” or the “Company”) on the terms of the change in your employment status with Mercury.

1. Your term of full time employment at Mercury, and your role as Chief Operating Officer and your service on the Board of Directors, will end effective December 31, 2003 (the “Transition Date”). After the Transition Date, you will have 30 days to exercise your vested stock options in accordance with the terms of the applicable option agreement, except as provided in Section 2(b) below. You will be eligible for COBRA coverage commencing January 1, 2004. On or before December 31, 2003, you will be paid your accrued vacation of $185,455.78.

2. Although you are not otherwise entitled to it, in consideration of your acceptance of this Agreement, Mercury will provide you with the following:

(a) During the period from January 1, 2004 through October 3, 2005 (the “Transition Period”), Mercury will pay you $29,166.67 per month in accordance with Mercury’s standard payroll practices, less applicable taxes. You will also receive (at or about the same time as the date it is paid to other Mercury executives), your annual bonus of $250,000.00 for the year ending December 31, 2003. Thereafter, you will also receive a similar bonus payment for the year ending December 31, 2004 (paid at 100% or such other percentage as the other Mercury executives receive based on the Company’s performance for that year), when other executives are paid their bonuses for 2004. Finally, you will receive a pro-rated bonus for 2005 in the amount of $187,500.00 (or an amount equal to the prorated portion of your annual bonus for 2005 paid at the same percentage rate as the other Mercury executives receive based on the Company’s performance) at the end of the Transition Period. Please note that all bonus payments are subject to all appropriate tax and related withholding requirements.

(b) Those stock options that would have otherwise vested during the Transition Period (as set forth on Exhibit B, the “Accelerated Options”) will be accelerated and shall be vested immediately effective as of the date of the action of the Compensation Committee of the Board of Directors (and in any event prior to December 31, 2003). Notwithstanding the terms of your option agreement, the Accelerated Options shall be exercisable until October 3, 2005. In addition, the vested portion of your stock option to purchase 350,000 shares with an exercise price of $60.875 that was granted on January 8, 2001 (the “Underwater Option”) shall also be exercisable until October 3, 2005. There are no changes to any options other than the Accelerated Options and the Underwater Option.

(c) Your laptop, RIM and cell phone will become your personal property.

(d) Mercury will transfer ownership of the Mercedes Benz CL500 that Mercury purchased for your business use to you promptly after December 31, 2003 provided, however, that Mercury will withhold from your salary, bonus or other amounts due to you by Mercury all applicable taxes on such car based on the then Kelly Blue Book value (expected to be no more than approximately $77,000).

(e) The parties acknowledge that the outstanding loan from stock option exercises has been paid in full.

Page 1

(f) Upon a Change of Control (as defined on Exhibit A), all consideration due and owing under this letter agreement will accelerate and become immediately due and payable to you.

3. You agree that the Change of Control Agreement between you and Mercury dated July 22, 1998 is terminated effective as of December 31, 2003.

4. You hereby affirm all of the provisions set forth in the Mercury Interactive Corporation Proprietary Information Agreement that you signed upon joining the Company as copy of which is attached hereto as Exhibit A.

5. You further agree, in exchange for the benefits provided above, that until the end of the Transition Period:

(a) you will not work for any business, whether as an employee, consultant or advisor, that is a competitor of Mercury. Competition is defined as: companies that sell application management (application performance management), application delivery (testing, tuning and deployment assurance) or IT Governance products and services including such companies as: Computer Associates, Compuware, BMC, Empirix, IBM, IBM Global Services, IBM Software, Keynote, Micromuse, Quest, Radview, Segue and Tivoli.

(b) and for a period of twelve (12) months thereafter, you will not personally solicit or recruit any of the Company’s employees to leave their employment (provided that for this purpose, a general employment advertisement by an entity of which you are a part will not constitute solicitation or recruitment and nothing in this Section 5(b) shall prevent any entity of which you are a part from hiring a Company employee).

(c) you agree that you will not actively counsel or assist any attorneys or their clients in the presentation or prosecution of any disputes, differences, grievances, claims, charges, or complaints by any third party against the Company and/or any officer, director, employee, agent, representative, shareholder or attorney of the Company, unless under a subpoena or other court order to do so or unless otherwise required by law to do so.

(d) if you materially breach any of the terms of this Agreement, that you, from the time of such material breach forward, shall not be entitled to any further payments or benefits under this Agreement, including but not limited to any further vesting under Mercury’s stock option plan; provided however, that in the case of a material breach, Mercury will provide you with written notice of such breach and you shall have 10 days from the date of such notice to cure such material breach (if such breach is capable of being cured).

6. With the exception of the breach of this Agreement by Mercury, you waive and release and promise never to assert any and all claims that you have or might have against Mercury and its predecessors, subsidiaries, related entities, officers, directors, shareholders, agents, attorneys, employees, successors, or assigns (collectively, the “Released Parties”), arising from or related to your employment with Mercury (other than your rights to receive your account balance under the Mercury 401(k) plan) and/or the termination of your employment with Mercury or any other claim that arises after the effective date of this Agreement.

These claims include, but are not limited to, claims arising under federal, state and local statutory or common law, such as the California Fair Employment and Housing Act, the California Labor Code, Title VII of the Civil Rights Act of 1964; the Americans with Disabilities Act, and the law of contract and tort (collectively, the “Released Claims”).

You agree that you will not file (or ask or allow anyone to file on your behalf), any charge, complaint, claim or lawsuit of any kind in connection with any claim released by this Agreement. This provision shall not apply, however, to any non-waivable charges or claims brought before any governmental agency. With respect to any such non-waivable claims, you agree to waive your right (if any) to any monetary or other recovery should any governmental agency or other third party pursue any claims on your behalf, either individually, or as part of any collective action. Nothing herein shall preclude any claim you may file alleging that your waiver of claims under the Age Discrimination in Employment Act of 1967 (“ADEA”) was not knowing or voluntary.

Page 2

You understand that the Released Claims include not only claims presently known to you, but also include all unknown claims and causes of action of any kind which would otherwise come within the scope of the Released Claims as described in above in this section 6. You therefore waive your rights under section 1542 of the Civil Code of California, which states:

A general release does not extend to claims which the creditor does not know or suspect to exist in his favor at the time of executing the release, which if known to him must have materially affected his settlement with the debtor.

7. You will not, unless required or otherwise permitted by law, until after such time as the terms of this agreement have been publicly disclosed by Mercury, disclose to others any information regarding the terms of this Agreement, the benefit being paid under it or the fact of its payment, except that you may disclose this information to your attorney, accountant or other professional advisor to whom you must make the disclosure in order for them to render professional services to you. You will instruct them, however, to maintain the confidentiality of this information just as you must.

8. You and Mercury agree to work together on a mutually acceptable press release regarding your transition from the Company. You and Mercury, its officers and directors, agree to refrain from any disparagement, criticism, defamation, slander of the other or tortious interference with the contracts and relationships of the other. In discussing your employment with and transition from the Company, you, Mercury and Mercury’s officer and directors will not in any material way, deviate from or expand upon the discussion in the press release.

9. Unless accepted in the manner set forth below on or before December 31, 2003, this Agreement will expire and become of no further legal effect or consequence.

To accept the agreement, please date and sign this letter and return it to me. Ken, I hope that we will be able to part ways on these amicable terms. Mercury Interactive Corporation and I wish you every success in your future endeavors.

Very truly yours,

By signing this letter, I acknowledge that I have had the opportunity to review this Agreement carefully with an attorney of my choice, that I understand the terms of the agreement, and that I voluntarily agree to them.

Dated: 12/30/03

Page 3

EXHIBIT A

Definition of “Change of Control”.

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

(a) Any “person” (as such term is used in Sections 13(d) and 14(d) of the Securities Exchange Act of 1934, as amended), excluding existing beneficial owners as of the date of this Letter, is or becomes the “beneficial owner” (as defined in Section 13d-3 of 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, excluding conversion of any convertible securities issued as of the date of this Letter;

(b) The composition of the Board of Directors changes during any period of 36 months such that individuals who at the beginning of the period were members of the Board of Directors (the “Continuing Directors”) cease for any reason to constitute at least a majority thereof; unless at least 66 ²/3% of the Continuing Directors has either (i) approved the election of the new Directors, (ii) if the election of the new Directors is voted on by shareholders, recommended that the shareholders vote for approval, or (iii) otherwise determined that such change in composition does not constitute a Change of Control, even if the Continuing Directors do not constitute a quorum of the whole Board (it being understood that this requirement shall not be capable of satisfaction unless there is at least one Continuing Director);

(c) The shareholders of the Company approve a merger or consolidation of the Company with any other corporation, other than a merger or consolidation which would result in the voting securities of the Company outstanding immediately prior thereto continuing to represent (either by remaining outstanding or by being converted into voting securities of the surviving entity) at least 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, or the shareholders of the Company approve 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;

(d) Any other provision of this subsection notwithstanding, the term Change of Control shall not include either of the following events undertaken at the election of the Company:

(i) Any transaction, the sole purpose of which is to change the state of the Company’s incorporation; or

(ii) A transaction, the result of which is to sell all or substantially all of the assets of the Company to another corporation (the “surviving corporation”) provided that the surviving corporation is owned directly or indirectly by the shareholders of the Company immediately following such transaction in substantially the same proportions as their ownership of the Company’s common stock immediately preceding such transaction.

Page 4

EXHIBIT B

Accelerated Options

Page 5