Exhibit 10.1

ROBERT HALF INTERNATIONAL INC.

Annual Performance Bonus Plan

(As Amended and Restated)

1. DEFINITIONS. As used in this Plan, the following terms shall have the meanings set forth below:

Administrator means the Compensation Committee of the Board of Directors of the Company, or such other Committee as may be appointed by the Board.

Annual Determination means the Target EPS and Target Bonuses determined annually by the Administrator, as described in Section 4 of this Plan.

Award Date means the date that the Administrator makes its written certification of a Bonus pursuant to Section 5 or Section 6.

Bonus means a Preliminary Bonus, a Final Bonus, or both.

Bonus Year means the fiscal year with respect to which a Bonus is paid pursuant to the Plan.

Company means Robert Half International Inc., a Delaware corporation.

Eligible Executive means (a) any elected executive officer of the Company and (b) any executive of the Company who has senior management functions and responsibilities, as designated by the Administrator.

EPS means diluted earnings per share, determined in accordance with generally accepted accounting principles. For purposes of the foregoing sentence, earnings shall mean income before extraordinary items, discontinued operations and cumulative effect of changes in accounting principles and any other objectively verifiable adjustment(s) thereto permitted and pre-established by the Administrator in accordance with Section 162(m) of the Internal Revenue Code of 1986, as amended, and after full accrual for the bonuses paid under this Plan. Earnings shall also be determined, with respect to any Target Bonus without regard to the effects of mergers, acquisitions, dispositions and material restructuring of the business occurring after the Target EPS for such Target Bonus was established.

Final Bonus means the Year-End Bonus less the Preliminary Bonus, but only if such number is greater than zero.

Final EPS means EPS calculated as of the end of a fiscal year.

Final Multiplier means (a) the Final Ratio, if the Final Ratio is greater than or equal to .5 and less than or equal to 2, (b) 2, if the Final Ratio is greater than 2, or (c) 0, if the Final Ratio is less than .5.

Final Ratio means the result obtained by dividing Final EPS by Target EPS.

Nine-Month Period means the first three fiscal quarters of the Bonus Year.

Plan means this Annual Performance Bonus Plan.

Potential Preliminary Bonus means, with respect to each Eligible Executive, 85% of the Product of the Preliminary Multiplier and such Eligible Executive’s Target Bonus, but in no event may such amount be in excess of $9,000,000.

Potential Year-End Bonus means, with respect to each Eligible Executive, the product of the Final Multiplier and such Eligible Executive’s Target Bonus, but in no event may such amount be in excess of $9,000,000.

Preliminary Bonus means, with respect to each Eligible Executive, that amount that the Administrator determines in accordance with Section 5 hereof, but in no event may such amount be in excess of $9,000,000.

Preliminary EPS means 1.334 multiplied by EPS for a Nine-Month Period.

Preliminary Multiplier means (a) the Preliminary Ratio, if the Preliminary Ratio is greater than or equal to .5 and less than or equal to 2, (b) 2, if the Preliminary Ratio is greater than 2, or (c) 0, if the Preliminary Ratio is less than .5.

Preliminary Ratio means the result obtained by dividing Preliminary EPS by Target EPS.

Repayment Amount means that amount calculated in accordance with Section 7.3 hereof.

Target Bonus means that amount set forth, with respect to each Eligible Executive, in an Annual Determination.

Target EPS means the EPS goal set annually by the Administrator, as set forth in an Annual Determination.

Year-End Bonus means, with respect to each Eligible Executive, that amount that the Administrator determines in accordance with Section 6 hereof, but in no event may such amount be in excess of $9,000,000.

2. PURPOSE. The purpose of the Plan is to attract, retain and motivate key senior management employees by providing additional compensation, in accordance with the terms and conditions set forth herein, based on the Company’s earnings.

3. ADMINISTRATION. The Administrator is authorized to construe and interpret the Plan, to prescribe, amend and rescind rules and regulations relating to the Plan, and to make all determinations and to take all actions necessary or advisable for the Plan’s administration. Whenever the Plan authorizes or requires the Administrator to take any action, make any determination or decision, or form any opinion, then any such action, determination, decision or opinion by or of the Administrator shall be in the absolute discretion of the Administrator and shall be final and binding upon all persons in interest, including the Company and all Eligible Executives.

4. ANNUAL DETERMINATION. On an annual basis, not later than the end of the first fiscal quarter of the Bonus Year, the Administrator shall determine the following with respect to the Bonus Year:

(i) the Eligible Executives;

(ii) the Target EPS for the Bonus Year;

(iii) the Target Bonus for the Bonus Year for each Eligible Executive; and

(iv) such other matters as are appropriate with respect to the Plan (together, the “Annual Determination”).

5. DETERMINATION OF PRELIMINARY BONUS. Within five business days after the public release by the Company of its audited results for the third fiscal quarter of the Bonus Year, the Chief Financial Officer shall (a) calculate the Preliminary EPS, (b) determine the Preliminary Multiplier for the Bonus Year, (c) calculate, with respect to each Eligible Executive, his Potential Preliminary Bonus, (d) deliver each calculation to the

Administrator. The Administrator shall, prior to the end of the Bonus Year, review the information submitted by the Chief Financial Officer and certify, in writing, each Eligible Executive’s Preliminary Bonus, which, except as provided in the next sentence, shall be the Potential Preliminary Bonus. Notwithstanding the foregoing, if any Eligible Executive’s Preliminary Bonus would be greater than his Target Bonus, the Administrator, in its sole discretion, may reduce the Preliminary Bonus of such Eligible Executive to such amount that is not less than the Target Bonus as it may determine.

6. DETERMINATION OF YEAR-END BONUS. Within ten business days after the public release by the Company of its audited results for the Bonus Year, the Chief Financial Officer shall (a) calculate the Final EPS, (b) determine the Final Multiplier for the Bonus Year, (c) calculate, with respect to each Eligible Executive, the Potential Year-End Bonus and (d) deliver such calculations to the Administrator. The Administrator shall, within 90 days of the end of the Bonus Year, review the information submitted by the Chief Financial Officer and certify, in writing, each Eligible Executive’s Year-End Bonus, which shall be the Potential Year-End Bonus; provided, however, that if any Eligible Executive’s Potential Year-End Bonus is greater than such Eligible Executive’s Preliminary Bonus, the Administrator may, in its sole discretion, reduce such Year-End Bonus to such amount that is not less than the Eligible Executive’s Preliminary Bonus as the Administrator may determine.

7. BONUS PAYMENTS. Each Eligible Executive shall be paid a Bonus in accordance with the following:

7.1. Preliminary Bonus. The Company shall pay the Preliminary Bonus to each Eligible Executive after such Preliminary Bonus is certified by the Administrator but prior to the end of the Bonus Year. Notwithstanding the foregoing, or anything appearing elsewhere herein, if an Eligible Executive is not employed by the Company on the date that Preliminary Bonuses are certified by the Administrator, then a pro-rated Preliminary Bonus shall be paid to such Eligible Executive (a) if the termination of employment was by reason of the Eligible Executive’s death, (b) as provided by any agreement or arrangement in existence on the date the Plan was approved by the stockholders or (c) under such circumstances as the Administrator, in its sole discretion, may determine; otherwise, no Preliminary Bonus in any amount shall be paid to such Eligible Executive.

7.2. Final Bonus. The Company shall pay the Final Bonus to each Eligible Executive after such Final Bonus is certified by the Administrator but prior to the fifteenth day of the third month following the end of the Bonus Year. Notwithstanding the foregoing, or anything appearing elsewhere herein, if an Eligible Executive is not employed by the Company on the last day of the Bonus Year, then a pro-rated Final Bonus shall be paid to such Eligible Executive (a) if the termination of employment was by reason of the Eligible Executive’s death, (b) as provided by any agreement or arrangement in existence on the date the Plan was approved by the stockholders or (c) under such circumstances as the Administrator, in its sole discretion, may determine; otherwise, no Final Bonus in any amount shall be paid to such Eligible Executive.

7.3. Repayment of Preliminary Bonus. If the Year-End Bonus for an Eligible Executive is less than such Eligible Executive’s Preliminary Bonus, such Eligible Executive shall repay such difference (the “Repayment Amount”) within fifteen (15) business days of notification thereof. To the extent the Repayment Amount is unpaid, the Company shall, consistent with applicable law, be entitled to deduct the Repayment Amount from any other amounts due by the Company to such Eligible Executive, and to pursue any and all other legal and equitable remedies to recover such Repayment Amount.

8. EMPLOYMENT. The selection of an employee as an Eligible Executive shall not affect any right of the Company to terminate, with or without cause, such person’s employment at any time.

9. WITHHOLDING TAXES. The Company shall, to the extent permitted by law, have the right to deduct from a Bonus any federal, state or local taxes of any kind required by law to be withheld with respect to such Bonus.

10. AMENDMENT, SUSPENSION OR TERMINATION OF THE PLAN. The Administrator may at any time amend, alter, suspend, or discontinue this Plan.

11. INDEMNIFICATION OF ADMINISTRATOR. Indemnification of members of the group constituting the Administrator for actions with respect to the Plan shall be in accordance with the terms and conditions of separate indemnification agreements, if any, that have been or shall be entered into from time to time between the Company and any such person.

12. HEADINGS. The headings used in this Plan are for convenience only, and shall not be used to construe the terms and conditions of the Plan.