ROBERT HALF INTERNATIONAL INC. AMENDMENT TO RESTRICTED SHARE AGREEMENT

EXHIBIT 10.1

ROBERT HALF INTERNATIONAL INC.

AMENDMENT TO RESTRICTED SHARE AGREEMENT

This Amendment to Restricted Share Agreement (the “Amendment”) is made and entered into effective as of May 9, 2012, by and between Harold M. Messmer, Jr. (“Participant”) and Robert Half International Inc. (the “Company”) and reflects the cumulative effects of amendments made effective May 6, 2012, and May 9, 2012.

For good and valuable consideration, to the sufficiency of which the parties acknowledge and agree, the Restricted Shares Agreements between Participant and the Company dated as of February 12, 2009, February 10, 2010, February 9, 2011, and April 12, 2012, (respectively, the “2009 Agreement”, the “2010 Agreement”, the “2011 Agreement” and the “2012 Agreement”) are amended as set forth below.

1.    Accelerated Vesting.    Section 3 of each of the 2009 Agreement, the 2010 Agreement, the 2011 Agreement and the 2012 Agreement is amended to insert “(excluding the first sentence of Section 15, which shall not apply to the Restricted Stock Award)” after “Section 15 of the Plan”.

2.    Performance Conditions.    Section 4 of the 2012 Agreement is hereby amended and restated in its entirety as follows:

“The Restricted Share Award shall be subject to the Performance Condition as specified in Section 12 of the Plan; provided, however, for purposes of this Restricted Share Award, the term “Multiplier” shall mean (a) the Performance Goal Ratio, if the Performance Goal Ratio is greater than or equal to 0 and less than 1.0, (b) 1, if the Performance Goal Ratio is greater than or equal to 1.0, or (c) 0, if the Performance Goal Ratio is less than 0. The Target Performance Goal (with respect to which the Performance Goal shall be Earnings Per Share) and the Performance Period shall be determined by the Committee.”

3.    Negative Discretion.    The 2011 Agreement and the 2012 Agreement are each hereby amended to add a new Section 19 to the end thereof:

“19.    Additional Negative Discretion.    In addition to the Performance Conditions set forth in Section 4 above and notwithstanding the vesting schedule set forth in Section 2 of the Agreement or anything to the contrary in the Plan, upon each vesting date, if the determination by the Compensation Committee of the TSR referred to below shall not yet have occurred, 50% of the shares that would otherwise be eligible to vest on such date (i.e., 25% of the total shares subject to the Restricted Share Award) shall remain held in escrow by the Company and subject to forfeiture based on the Company’s Total Shareholder Return (“TSR”) relative to the TSR of the companies that comprise the S&P 500 Index as of May 6, 2012 and December 31, 2014 (the “S&P 500 TSR”) for the period commencing on May 6, 2012 and ending on December 31, 2014 (the “TSR Measurement Period”). The calculation of the Final Award and the total number of shares that may be forfeited, if any, based on the Company’s relative TSR shall be determined as follows:

(i) if the Company’s TSR for the TSR Measurement Period is at or below the 35^th percentile relative to the S&P 500 TSR, then 50% of the total shares remaining subject to the Restricted Share Award after any adjustment for the Performance Condition specified in Section 4 shall be forfeited in calculating the Final Award;

(ii) if the Company’s TSR for the TSR Measurement Period is at or above the 50^th percentile relative to the S&P 500 TSR, then no shares subject to the Restricted Share Award shall be forfeited in calculating the Final Award as a result of the Company’s TSR; and

(iii) to the extent the Company’s TSR for the TSR Measurement Period is between the 35^th and 50^th percentile relative to the S&P 500 TSR, linear interpolation shall be used to determine the percentage of shares remaining subject to the Restricted Share Award after any adjustment for the Performance Condition specified in

Section 4 that shall be forfeited. For example, if the Company’s relative TSR is at the 40^th percentile, then 33.3% of the total shares remaining subject to the Restricted Share Award shall be forfeited.

Any non-forfeited shares held in escrow pursuant to this Section 19 shall be released upon the Compensation Committee’s determination of the Company’s TSR shortly following the completion of the TSR Measurement Period. For the avoidance of doubt, the total number of shares that may be forfeited pursuant to this Section 19 shall be allocated equally between the tranches scheduled to vest on each of the two vesting dates.

For purposes of this Restricted Share Award, “Total Shareholder Return” or “TSR” shall be equal to the average price of a share of common stock during the thirty (30) trading days prior to and ending on the last trading day on or immediately prior to the last day of the TSR Measurement Period less the average price of a share of common stock during the thirty (30) trading days prior to and ending on the last trading day on or immediately prior to the first day of the TSR Measurement Period, plus all dividends payments made during the TSR Measurement Period, which are assumed to be re-invested as of the date of such dividend distribution, divided by the average price of a share of common stock during the thirty (30) trading days prior to and ending on the last trading day on or immediately prior to the first day of the TSR Measurement Period, with all prices to be automatically proportionately adjusted as applicable in the event of a stock split, reverse stock split, combination, consolidation, reclassification or subdivision.”

4.    Adjustment of Grant.    The 2011 Agreement is amended to reduce the number of shares covered thereby from 178,037 to 136,146. The 41,891 shares no longer covered by the 2011 Agreement are deemed forfeited without consideration and shall be returned to the Company. The 136,146 shares still subject to the agreement shall vest as to 50% thereof on each of the two vesting dates specified in Section 2 of the 2011 Agreement.

5.    Full Force and Effect.    To the extent not expressly amended hereby, the 2009 Agreement, the 2010 Agreement, 2011 Agreement and the 2012 Agreement remain in full force and effect.

IN WITNESS WHEREOF, the parties hereto have executed this Agreement as of the date first written above.

Participant hereby accepts and agrees to be bound by all of the terms and conditions of this Agreement.