AMENDED AND RESTATED DEFERRED COMPENSATION PLAN

EXHIBIT 10.4

AMENDED AND RESTATED

DEFERRED COMPENSATION PLAN

OF

ROBERT HALF INTERNATIONAL INC.

(As Amended and Restated Effective July 29, 2008)

1. DEFINITIONS.

As used in this Plan, the following terms have the meanings set forth below:

1.1 Administrator means a committee appointed by the Board and composed of independent members of the Board who are not employees of the Company.

1.2 Board means the Board of Directors of the Company.

1.3 Code means the Internal Revenue Code of 1986, as amended.

1.4 Company means Robert Half International Inc.

1.5 KERP means the Company’s Key Executive Retirement Plan—Level II that was previously maintained for the Participant until it was merged into this Plan effective October 1, 2006.

1.6 Participant means the individual who was the Company’s Chief Executive Officer as of October 1, 2006.

1.7 Plan means this Amended and Restated Deferred Compensation Plan.

1.8 Restated Retirement Agreement means the retirement agreement, as amended effective October 1, 2006, that was entered into by and between the Company and the Participant pursuant to the KERP.

1.9 Trust Agreement means the Amended and Restated Trust Agreement under the Robert Half International Inc. Amended and Restated Deferred Compensation Plan between the Company and U.S. Trust Company of California, N.A., effective October 1, 2006.

2. PURPOSE OF THE PLAN. The purpose of the Plan is to retain and reward the Participant by offering flexible compensation opportunities and to incentivize the Participant to remain with the Company until retirement. Effective as of October 1, 2006, the KERP merged into this Plan and the Company’s obligation to the Participant under the KERP and Restated Retirement Agreement will instead entirely be satisfied through this Plan. Effective January 1, 2005 and to the extent applicable, the Plan is intended to satisfy the requirements of, and shall be implemented and administered in a manner consistent with, Section 409A of the Code.

3. ADMINISTRATION. The Administrator shall have full power to interpret, construe and administer the Plan, except as otherwise provided in the Plan. The expense of administering the Plan shall be borne by the Company and shall not be charged against benefits payable hereunder.

4. ELIGIBILITY AND PARTICIPATION. The Plan will cover the Participant. The fact that the Participant is also a director of the Company or a subsidiary shall not prevent his participation.

5. DEFERRED COMPENSATION FORMULA. The amount of deferred compensation that the Participant will be allocated under the Plan for each calendar year of participation shall be based on a percentage of the Participant’s total annual base salary and annual cash bonus income payable to the Participant for services rendered during such calendar year and the performance of the Company as compared to the goal for the year established by the Board according to the following schedule:

The Company goal for each year will be established by the Compensation Committee of the Board. Such allocation shall be deemed to have been made, for all purposes relating to this Plan, as of the first business day of the year following the year with respect to which the deferred compensation has been earned. Calculation and allocation of deferred compensation pursuant to the above formula shall be completed within 105 days following year end.

6. SEPARATE ACCOUNTS. The Administrator shall maintain an individual account under the name of the Participant (the “First Account”). The First Account shall be adjusted to reflect deferred compensation credited under Section 5 through December 31, 2004, interest credited on such amounts and any distribution of such amounts hereunder. Effective January 1, 2005, the First Account shall cease to be credited with deferred compensation allocations under Section 5 although the First Account will continue to be adjusted for interest crediting and distributions.

Effective January 1, 2005, the Administrator shall maintain an additional individual account, separate and apart from the First Account, under the name of the Participant (the “Second Account”). The Second Account shall be adjusted to reflect deferred compensation credited under Section 5 on or after January 1, 2005, interest credited on such amounts and any distribution of such amounts hereunder.

Effective October 1, 2006, the Administrator shall establish and maintain an additional individual account, separate and apart from the First Account and Second Account, under the name of the Participant (the “KERP Account”). On October 1, 2006, the KERP Account shall be credited with a starting bookkeeping balance that is equal to the “Converted Lump Sum Amount” (as defined under the Restated Retirement Agreement) and such starting balance shall be $48,981,459. The KERP Account shall be adjusted to reflect interest crediting and any distributions. The KERP Account shall not be credited with any deferred compensation allocations that is provided to the other individual accounts pursuant to Section 5.

The First Account, Second Account and KERP Account shall each separately be adjusted on the last day of each calendar quarter to reflect interest accrued on the balance of such accounts as of the last day of the previous calendar quarter, including any amount of deferred compensation and interest which accrued before the end of such previous calendar quarter. In addition, for the calendar year ending December 31, 2006, the KERP Account shall be adjusted on December 31, 2006 to reflect interest accrued on the balance of such account as of October 1, 2006.

The establishment and maintenance of the foregoing separate individual accounts for the Participant shall not be construed as giving the Participant any interest in any assets of the Company or any right to payment other than as provided hereunder or any right to participate hereunder in future years of employment. Such individual accounts shall be unfunded and maintained only for bookkeeping convenience.

Interest credited for a calendar quarter shall be at a rate equal to the 10+ Year High Quality yield for the valuation reporting date which coincides with or immediately precedes the last day of such calendar quarter as expressed in the Merrill Lynch Bond Index reported by The Wall Street Journal.

7. VESTING. The Participant’s interest under the Plan, including future crediting of deferred compensation and/or interest, is vested and nonforfeitable hereunder.

8. TIME OF DISTRIBUTION. Subject to Section 9, no amount shall be payable hereunder until the first to occur of the following events:

(a) The date of the Participant’s disability determined by the Administrator in accordance with Section 409A of the Code and applicable guidance and Treasury regulations promulgated thereunder;

(b) The Participant’s death; or

(c) The date of the Participant’s separation from service (notwithstanding Participant’s entering into a Part-Time Employment Agreement), determined by the Administrator in accordance with Section 409A of the Code and applicable guidance and Treasury regulations promulgated thereunder.

All vested amounts will be valued and paid within 30 days following the occurrence of any such event; provided, however, that amounts in the Second Account and KERP Account that are payable upon a separation from service shall be valued and paid (to the extent required by Section 409A of the Code) 6 months following such separation from service (and both such accounts shall continue to accrue interest during such 6 month period). If distribution occurs within 105 days after the end of any calendar year and, as a result, the Participant’s accounts do not include the amount allocable to the prior year, a pro-rata amount (based on the Participant’s method of distribution) of the vested portion of such prior year amount will be paid to the Participant promptly following its calculation pursuant to the Plan and in no event later than March 15 of the following year.

9. FINANCIAL NECESSITY DISTRIBUTIONS. Notwithstanding Section 8, the Administrator may direct payment of all or any portion of amounts credited to the Participant’s accounts prior to his separation from service after application by the Participant. Any such application must show demonstrable financial need for distribution: (i) for the First Account, the amount needed to meet extraordinary medical or medically-related expenses, substantial costs related to residential requirements of the Participant, family educational expenses must be considered by the Administrator burdensome in relation to the Participant’s other available financial resources for meeting such expenses, extraordinary expenses related to an unanticipated casualty, accident or other misfortune or any other similar need approved by the Administrator; and (ii) for the Second Account or KERP Account, the amount must be needed for an unforeseeable emergency as defined under Code Section 409A and applicable regulations promulgated thereunder.

10. METHOD OF DISTRIBUTION.

(a) First Account. Upon separation from service, the Participant shall be eligible to receive a lump-sum distribution of all amounts payable under the First Account. Notwithstanding the foregoing, the Participant may elect to have payment in the form of installments over a period of time not extending beyond the life expectancy of the Participant. To be effective, any election(s) to change the form of payment must be made at least 12 months before the Participant’s separation from service and payments under the new election must commence at least 12 months after the date the Participant makes the new election.

(b) Second Account and KERP Account. Upon separation from service and subject to Section 8, the Participant shall be eligible to receive a lump-sum distribution of all amounts payable under the Second Account and the KERP Account. Notwithstanding the foregoing, the Participant may elect (prior to January 1, 2009) in accordance with procedures prescribed by the Internal Revenue Service to have payment of either the Second Account and/or the KERP Account in the form of installments over a period of time not extending beyond the life expectancy of the Participant and, to the extent required by Section 409A of the Code and any Treasury regulations promulgated thereunder, payments under such election must commence at least 12 months after the date the Participant makes this election. Any subsequent election(s) (made after December 31, 2008) to change the form of payment shall not become effective for 12 months from the date

the election is made and payments under any such new election(s) must be delayed for at least five years after the payments otherwise would have commenced (except that such five year delay is no longer applicable upon the Participant’s death or disability (as defined under Code Section 409A)) . Notwithstanding the foregoing, a change in form of payment for an account under this Section 10(b) shall not accelerate payment of such account, except as allowed by Section 409A of the Code and the Treasury regulations promulgated thereunder.

(c) Elections. Any change in payment election(s) made under this Section 10 shall be made in writing and the date of such election(s) shall be the date the election is received by the Administrator.

11. DEATH OF PARTICIPANT. In the event of the Participant’s death at any time prior to the complete distribution of all amounts payable to him hereunder, all unpaid amounts shall be paid in a single lump-sum to the beneficiary or beneficiaries designated by the Participant or to his estate in the absence of any such designation. The Participant shall have the right to designate a beneficiary (or beneficiaries) in the event of his death; provided that in the event that the Participant is married and designates a beneficiary other than his spouse, his spouse must have provided the Administrator with written consent to such designation.

12. PAYMENT IN THE EVENT OF DISABILITY. If the Participant is entitled to any payment hereunder and is under a legal disability, or in the sole judgment of the Administrator shall otherwise be unable to apply such payment to his own interest and advantage, the Administrator in the exercise of its discretion may direct the Company to make any such payment in any one (1) or more of the following ways:

(a) Directly to the Participant;

(b) To the Participant’s legal guardian or conservator; or

(c) To the Participant’s spouse or to any person charged with his support; to be expended for the benefit of the Participant. The decision of the Administrator shall in each case be final and binding upon all persons in interest. Any such payment shall completely discharge the obligations of the Administrator and Company with regard to such payment.

13. ASSIGNMENT. No Participant or beneficiary of the Participant shall have any right to assign, pledge, hypothecate, anticipate or in any way create a lien upon any amounts payable hereunder. No amounts payable hereunder shall be subject to assignment or transfer or otherwise be alienable, either by voluntary or involuntary act or by operation of law, or subject to attachment, execution, garnishment, sequestration or other seizure under any legal, equitable or other process, or be liable in any way for the debts or defaults of the Participant and his beneficiaries.

14. WITHHOLDING. Any taxes required to be withheld from payments to the Participant hereunder shall be deducted and withheld in amounts determined by the Company.

15. OTHER BENEFIT PLANS OF THE COMPANY. Nothing contained in this Plan shall prevent the Participant prior to his death, or his dependents or beneficiaries after his death, from receiving, in addition to any payments provided for under this Plan, any salary, any payments under a Company retirement plan or any amounts otherwise payable or distributable to him, his dependents or beneficiaries, under any other plan or policy of the Company or otherwise. Nothing in this Plan shall be construed as preventing the Company from establishing any other or different plans providing for deferred compensation for the Participant or other employees.

16. AMENDMENT AND TERMINATION. This Plan may be amended in whole or in part by action of the Board and may be terminated at any time by action of the Board; provided, however, that no such amendment or termination shall reduce any amount payable hereunder or change the timing of any distribution to the extent such amount accrued prior to the date of amendment or termination or cause the Participant to incur any tax liability under the Code, including but not limited to Section 409A thereof; and provided further, that the duties and liabilities of the members of the Administrator hereunder shall not be increased without their written consent.

17. RIGHTS OF PARTICIPANT. The Company’s sole obligation to the Participant and his beneficiaries shall be to make payment as provided hereunder. All payments shall be made from the general assets of the Company, and the Participant shall have no right hereunder to any specific assets of the Company or to be retained in the employment of the Company. All amounts of compensation allocated under this Plan, any property purchased therewith and all income attributable thereto shall remain the property and rights of the Company subject to the claims of the Company’s general creditors.

18. BINDING PROVISIONS. All of the provisions of this Plan shall be binding upon all persons who shall be entitled to any benefits hereunder, and their heirs, and personal representatives.

19. INDEMNIFICATION OF COMMITTEE. Members of the group constituting the Administrator shall be indemnified for actions with respect to the Plan to the fullest extent permitted by the Restated Certificate of Incorporation, as amended, and the By- laws of the Company and by the terms of any indemnification agreement that has been or shall be entered into from time to time between the Company and any such person.

20. EFFECTIVE DATE. This Plan was originally effective for allocation of compensation with respect to the year beginning January 1, 1989.

21. GOVERNING LAW. This Plan and all determinations made and actions taken pursuant hereto shall be governed by the law of the State of California and construed accordingly.

22. SEVERABILITY. If any provision of this Agreement is held to be unenforceable for any reason, it shall be adjusted rather than voided, if possible, in order to achieve the intent of the parties to the extent possible. In any event, all other provisions of this Agreement shall be deemed valid and enforceable to the fullest extent possible.

23. DISPUTE RESOLUTION. Any dispute, controversy or claim arising under the Plan shall be definitively resolved in accordance with the arbitration provisions contained in Section 2(a) (`Payments to the Participant and His Beneficiaries’) of the Trust Agreement with references to the `Trust Agreement’ in such Section 2(a) being replaced by references to this Plan. Furthermore, if any such arbitration or action at law or in equity is brought to enforce or interpret the terms of the Plan, the prevailing party shall be entitled to reasonable attorneys’ fees, costs and necessary disbursements in an addition to any other relief to which it may be entitled. Upon written request by the Participant, the Company shall advance to Participant amounts equal to all reasonable attorneys’ fees, costs, and necessary disbursements incurred by Participant in seeking to obtain, enforce, or retain any right, benefit, or payment provided for in the Plan or in otherwise pursuing or settling any claim hereunder. If the Company is the prevailing party in any arbitration or action to enforce or interpret the Plan, the Participant shall reimburse the Company in the full amount of the advances made pursuant to the preceding sentence.

24. RABBI TRUST. Pursuant to the Trust Agreement, the Company established an irrevocable “grantor trust”. The Company has deposited with the trustee cash and/or property and these trust assets, subject to the provisions of the Trust Agreement, may be used to help satisfy the Company’s obligations to the Participant under the KERP Account.

Effective as of October 1, 2006, the Company shall calculate the percentage by which the assets in the Trust, taking into account those assets transferred to the Trust from the trust for the KERP, is less than the balance of the KERP Account(“Shortfall Percentage”). The Company shall then divide the Shortfall Percentage by 16 (“Quarterly Shortfall Percentage”), and no later than 60 days after the end of each calendar quarter following the quarter ending September 30, 2006, shall deposit sufficient additional amounts to the Trust so as to reduce the resulting Shortfall Percentage to the difference between the original Shortfall Percentage and the product of the Quarterly Shortfall Percentage and the number of calendar quarters following September 30, 2006 which difference shall be applied to the balance of the KERP Account at the end of such calendar quarter. In clarification and amplification of the foregoing, at the end of that calendar quarter ending September 30, 2010 and for each subsequent calendar quarter until the Company’s obligations hereunder have been satisfied in full, the value of the assets in the Trust shall be no less than the balance of the KERP Account on that same date, and

to the extent necessary, the Company shall use its best efforts to deposit sufficient additional amounts to the Trust as promptly as practicable in order to eliminate any such deficiency, but in no event shall make such deposit later than 60 days after the end of such calendar quarter.

Notwithstanding the foregoing, Participant shall have the right at any time to request that the Company deposit sufficient additional amounts such that the value of the assets in the Trust shall be at least equal to then current balance of the KERP Account. The Company’s obligation shall be effective upon the delivery of a written request from Participant to an officer of the Company. If such request is delivered, it shall trigger a deposit obligation on the part of the Company. The Participant’s delivery of such a request is sufficient in and of itself to trigger the Company’s deposit obligation, and no additional action need be taken or consent be obtained to trigger such obligation. The amount necessary to satisfy the Company’s deposit obligation shall be deposited in cash or property (reasonably acceptable to Participant) with the trustee as promptly as practicable, but in no event later than 60 days after the date such request is received by the Company.