Amended and Restated Severance Agreement (Effective as of April 21 , 2009)

EXHIBIT 10.3

Amended and Restated Severance Agreement

(Effective as of April 21 , 2009)

This Amended and Restated Severance Agreement is entered into as of April 21, 2009, by and between Robert Half International Inc., a Delaware corporation (the “Company”) and Paul F. Gentzkow (the “Employee”).

WHEREAS, the Company and Employee have previously entered into an Amended and Restated Severance Agreement dated as of July 29, 2008, which amended and restated an agreement originally entered into in 2000.

WHEREAS, the Severance Agreement was entered into because the Company believed it to be in the best interest of the Company and its shareholders to provide for stability in the management of the Company.

WHEREAS, the Compensation Committee of the Board of Directors of the Company has approved certain amendments to the Severance Agreement.

NOW, THEREFORE, in consideration of the foregoing and the terms and conditions set forth herein, the Company and the Employee hereby agree that the Amended and Restated Severance Agreement dated July 29, 2008, shall be amended and restated to read in its entirety as set forth herein:

1. Definitions

“Base Salary” means the highest rate of annual base salary paid to Employee at any time within the six (6) months preceding the Termination Date.

“Change in Control” shall have the meaning specified in the Company’s Stock Incentive Plan, as in effect on July 29, 2008.

“Continuation Number” means (a) 2.99, if Employee has served as a Director of the Company at any time prior to the Termination Date, and (b) 2, in all other cases.

“Earliest Payment Date” shall mean six months following Separation from Service or such alternate date as future modifications or amendments to Section 409A and the rules and regulations thereunder may specify as the earliest permitted date for a payment to be made, or, if earlier the date of Employee’s death.

“Medical Coverage” means healthcare insurance, benefits and/or coverage that either directly pays the cost of medical care or provides reimbursement therefor, and includes, but is not limited to, doctor or other provider services, tests, equipment, prescriptions and anything else generally considered to be related to individual health care, whether preventive or corrective.

“Section 409A” means Section 409A of the Internal Revenue Code.

“Separation from Service” shall have the meaning specified by Section 409A and the rules and regulations thereunder, as such meaning may be modified or amended from time to time.

“Specified Employee” shall have the meaning specified by Section 409A and the rules and regulations thereunder, as such meaning may be modified or amended from time to time.

“Stock” means the Common Stock, $.001 par value, of the Company.

“Termination Date” means the date on which Employee’s employment with the Company is terminated.

“Termination For Cause” means termination by the Company of Employee’s employment by the Company by reason of Employee’s willful dishonesty towards, fraud upon, or deliberate injury or attempted injury to the Company, or by reason of Employee’s willful material breach of any employment agreement with the Company, which has resulted in material injury to the Company; provided, however, that Employee’s employment shall not be deemed to have terminated in a Termination For Cause if such termination took place as a result of any act or omission believed by Employee in good faith to have been in the interest of the Company.

“Termination Without Cause” means (1) termination by the Company of Employee’s employment other than pursuant to a Termination For Cause or (2) termination by Employee following (a) a reduction by more than 5% of Employee’s base salary per month, exclusive of bonus, fringe benefits and other non-salary compensation, or (b) a request by the Company that Employee relocate more than 50 miles away from the current location of the principal executive offices of the Company.

“Termination Following a Change in Control” means a voluntary termination by Employee within one year following Change in Control.

2. Payments and Benefits Upon Termination Without Cause. In the event of a Termination Without Cause, the Employee shall be entitled to receive the following:

2.1. Base Salary. Employee shall be paid a lump-sum amount equal to the product of Employee’s Base Salary and Employee’s Continuation Number. To the extent required by Section 409A, if Employee is a Specified Employee, this lump sum shall be paid no earlier than the Earliest Payment Date and no later than ten business days thereafter.

2.2. Bonus.

(a) If the Termination Date occurs within 12 months after a Change in Control, Employee shall be paid a lump-sum amount equal to the product of (i) the annual cash bonus paid (or to be paid) to Employee with respect to the last full calendar year completed prior to the Change in Control and (ii) Employee’s Continuation Number. To the extent required by Section 409A, if Employee is a Specified Employee, this lump sum shall be paid no earlier than the Earliest Payment Date and no later than ten business days thereafter.

(b) If the Termination Date does not occur within 12 months after a Change in Control, Employee shall be paid, when such bonus payments would otherwise typically be made to Employee, but in no event later than the March 15 of the calendar year immediately following the Calendar year in which the Termination Date occurs, a lump-sum amount equal to the product of (i) a fraction, the numerator of which shall be the number of months that, as of the last day of the month in which the Termination Date occurs, shall have passed since the beginning of that calendar year, and the denominator of which shall be twelve and (ii) the bonus to which Employee would have been entitled had such termination not occurred. For purposes of the foregoing clause (ii), Employee shall be not be entitled to a pro rata amount of bonus that is discretionary unless such Employee is specifically awarded such discretionary amount in accordance with the terms and conditions of the applicable bonus plan or program.

2.3. Benefits. For such number of years following the Termination Date as is equal to the Continuation Number, or until Employee is reemployed, whichever first occurs, Employee also shall be entitled to all employee benefits, including medical and life insurance, pension, retirement and other benefits to which Employee was entitled on the Termination Date.

2.4. Vesting. If, on the Termination Date, Employee holds any Stock or options or other rights to acquire Stock which are subject to restrictions or vesting based on continued employment with the Company, such restrictions shall lapse and such vesting shall occur effective as of the Termination Date. Each option held by Employee shall remain outstanding and exercisable until the earlier of its exercise or its original expiration date. In addition, if Employee is a participant in the Company’s Deferred Compensation Plan, Senior Executive Retirement Plan or any successor plans, all amounts credited under such plans to Employee shall become fully vested and nonforfeitable.

2.5. Multiple Benefits. To the extent that any other agreement (“Other Agreement”) between the Employee and the Company would provide for salary continuation (or a lump sum payment in lieu of salary continuation) and bonus payments under the same circumstances as such benefits would be provided pursuant to Sections 2.1 and 2.2 hereof, then Employee shall not receive such benefits under both the Other Agreement and Sections 2.1 and 2.2, but shall instead receive the greater of the salary benefit payable under either Section 2.1 or the Other Agreement and the greater of the bonus benefit payable under either Section 2.2 or the Other Agreement.

Notwithstanding the foregoing, the Benefits provided by Sections 2.1, 2.2 and 2.3 hereof shall supersede the provisions of Sections 2.1 and 2.2 of the Severance Agreement dated as of October 1, 1991, between Employee and the Company and Sections 2(a), 2(b) and 2(c) of the Agreement dated as of July 31, 1995, between Employee and the Company, which superseded sections are of no further force or effect.

3. Termination Following a Change in Control. If Employee has served as a Director of the Company at any time prior to the Termination Date, Employee shall be entitled to the benefits described in Section 2 hereof in the event of a Termination Following a Change in Control.

4. Medical Coverage. In the event of any termination of Employee’s employment on or after (i) Employee’s 53^rd birthday (if Employee has served as a director) or (ii) Employee’s 60^th birthday (if Employee has not served as a director), whether by the Company or by Employee, other than a Termination For Cause, the Company shall continue to provide to each of Employee and his then current wife until their respective deaths, at the Company’s expense, Medical Coverage at a level equal to the greater of (a) the level provided at the date hereof or (b) whatever level may be provided by the Company at any time after the date hereof for its then current employees. Such Medical Coverage shall be provided by means of continued participation in Company healthcare plans, the provision of a separate healthcare plan, direct Company reimbursement, or any combination thereof.

5. Employment. The sole purpose of this Agreement is to provide Employee with severance benefits under the circumstances described herein. This Agreement is not an employment agreement. This Agreement shall not affect any right of the Company to terminate Employee’s employment at any time.

6. Headings. The headings used in this Agreement are for convenience only, and shall not be used to construe the terms and conditions of the Agreement.

7. Governing Law. This Agreement shall be governed by and construed according to the laws of the State of California. The terms of this Agreement shall bind and shall inure to the benefit of the successors and assigns of the parties hereto.

IN WITNESS WHEREOF, the Company and the Employee have executed this Agreement as of the date first set forth above.