QuickLinks -- Click here to rapidly navigate through this document

Exhibit 10.1

April 30, 2013

William C. Lucia
HMS Holdings Corp.
5615 High Point Drive
Irving, Texas 75038

Dear Bill:

        You and HMS Holdings Corp. (the "Company") are parties to an employment agreement effective as of March 1, 2013 that sets forth certain terms of your employment with the Company (the "Employment Agreement"). You and the Company have agreed to certain amendments to the Employment Agreement. Except as set forth below, your Employment Agreement shall remain in full force and effect.

        1.     The pre-amendment Employment Agreement provided that if your employment is terminated due to death, the termination of your employment will be treated as termination without Cause under Section 6(b) or 6(c). You and the Company have agreed to remove the possibility of severance benefits upon your death.

        Consistent with the foregoing, Section 6(e) of the Employment Agreement is amended and restated to read as follows:

"Death or Disability. The Executive's employment hereunder will terminate immediately upon his (i) death or (ii) Separation from Service due to Disability. "Disability" means the Company, based on appropriate medical evidence, determines he has become physically or mentally incapacitated so as to render him incapable of performing his usual and customary duties, with or without a reasonable accommodation, for 180 or more days, whether or not consecutive, during any 12 month period. The Executive is also disabled if he is found to be disabled within the meaning of the Company's long-term disability insurance coverage as then in effect (or would be so found if he applied for such coverage or benefits). Employment termination due to Disability is treated as termination without Cause under Section 6(b) or 6(c) as applicable. Nothing in this Section prevents the Board from removing the Executive from his position as CEO or, under Section 6(b), (c), or (d), from terminating his employment at any time, subject to compliance with those subsections when applicable."

        2.     The other provisions of the Employment Agreement remain in full force and effect.

Signatures on Page Following

Sincerely,
HMS Holdings Corp.
By:	/s/ ROBERT M. HOLSTER Robert M. Holster Chairman of the Board of Directors

        I have carefully read this amendment, understand the contents herein, freely and voluntarily assent to all of the terms and conditions hereof, and sign my name of my own free act.

/s/ WILLIAM C. LUCIA
William C. Lucia Date: April 30, 2013

QuickLinks

Exhibit 10.1

Signatures on Page Following