FIRST AMENDMENT TO EXECUTIVE EMPLOYMENT AGREEMENT

Exhibit 10.31

FIRST AMENDMENT TO EXECUTIVE EMPLOYMENT AGREEMENT

This First Amendment to Executive Employment Agreement (the “Amendment”) is made effective as of May 8, 2009, by and between Marchex, Inc., a Delaware corporation (“Marchex”), and Michael A. Arends (“Executive”), in order to amend the Executive Employment Agreement entered into between Marchex and Executive effective as of May 1, 2003 (the “Executive Employment Agreement”).

WHEREAS, the parties desire to enter into this Amendment to bring the provisions of the Executive Employment Agreement into documentary compliance with the applicable requirements of Section 409A of the Internal Revenue Code, as amended, and the Treasury Regulations issued thereunder (“Section 409A”).

NOW, THEREFORE, in consideration of the mutual covenants and promises herein contained, and for other good and valuable consideration, the receipt and sufficiency of which are hereby acknowledged, Marchex and Executive hereby agree as follows:

1. Section 5.02(b) the Executive Employment Agreement is amended in its entirety to read as follows:

(b) Termination Other than for Cause, or for Death, Disability or Good Reason. If (i) Executive ceases to be a Marchex employee on account of (A) Marchex’s termination of Executive’s employment other than for Cause, (B) Disability, (C) Executive’s death, or (ii) Executive resigns his employment with Marchex after giving Marchex notice of the occurrence of one or more events that constitute Good Reason within a reasonable period (but not more than ninety (90) days after such occurrence) and Marchex fails to correct such occurrence within a reasonable time (but not more than sixty (60) days) and Executive’s resignation occurs within ten (10) days after the expiration of that cure period, then in addition to the amounts payable under Section 5.02(a):

(A) The stock options held by Executive shall become fully vested, and

(B) If Executive ceases to be an employee within the first three (3) years of his employment, Marchex shall pay Executive, an amount equal to one fourth (1/4) of the amount that is Executive’s Salary. For each additional year after three (3) full years of employment, Executive shall be entitled to an additional amount equal to one twelfth (1/12) of the amount that is Executive’s Salary; provided, however, that in no event shall Executive be entitled to an amount equal to more than one (1) year’s Salary. Except as otherwise provided by Section 5.02(e), payment pursuant to this subsection (B) shall made on the tenth (10th) day following the date on which Executive ceases to be a Marchex employee.

2. Section 5.02 Executive Employment Agreement is amended to add at the end thereof the following new subsection (e):

(e) Separation from Service; Delay in Payment to Specified Employee. Notwithstanding anything set forth in this Section 5.02 to the contrary, no amount payable pursuant to this Section 5.02 on account of Executive’s termination of employment with Marchex which constitutes a “deferral of compensation” within the meaning of Section 409A shall be paid unless and until Executive has incurred a

“separation from service” within the meaning of Section 409A. Furthermore, if Executive is a “specified employee” within the meaning of Section 409A as of the date of the Executive’s separation from service, no amount that constitutes a deferral of compensation which is payable on account of Executive’s separation from service shall be paid to Executive before the date (the “Delayed Payment Date”) which is first day of the seventh month after the date of Executive’s separation from service or, if earlier, the date of Executive’s death following such separation from service. All such amounts that would, but for this Section 5.02(e), become payable prior to the Delayed Payment Date will be accumulated and paid on the Delayed Payment Date.

3. A new Section 9.09 is added to the Executive Employment Agreement to read as follows:

9.09 Compliance with Section 409A. Marchex intends that income provided to Executive pursuant to this Agreement will not be subject to taxation under Section 409A. The provisions of this Agreement shall be interpreted and construed in favor of satisfying any applicable requirements of Section 409A. However, Marchex does not guarantee any particular tax effect for income provided to Executive pursuant to this Agreement. In any event, except for the responsibility of Marchex to withhold applicable income and employment taxes from compensation paid or provided to Executive, Marchex shall not be responsible for the payment of any applicable taxes incurred by Executive on compensation paid or provided to Executive pursuant to this Agreement.

4. Except as set forth herein, all other terms and conditions of the Executive Employment Agreement will remain in full force and effect.

[Remainder of Page Intentionally Left Blank]

2

IN WITNESS WHEREOF, the parties hereto have duly executed this Amendment as a sealed instrument as of the day and year first above written.

3