CONSULTING AGREEMENT

Exhibit 10.1

CONSULTING AGREEMENT

This Consulting Agreement (the “Agreement”) is made and entered into effective as of June 1, 2004 (the “Effective Date”) at Houston, Texas between Sterling Bancshares, Inc., a Texas corporation (“Bancshares”), and George Martinez, an individual residing in Houston, Texas (“Consultant”).

WITNESSETH:

WHEREAS, Consultant is currently a director of Bancshares and its indirect subsidiary, Sterling Bank, a Texas banking association (“Bank”), and has been a senior executive officer of, and employed by, Bancshares and the Bank, including, pursuant to that certain Employment Agreement effective as of January 1, 2002 (the “Employment Agreement”);

WHEREAS, Consultant has notified Bancshares and the Bank of his desire to retire and resign from his current employment with Bancshares and the Bank pursuant to the Employment Agreement, such retirement and resignation to be effective on the date herein provided;

WHEREAS, Consultant is a director of Bancshares and the Bank and has been a senior executive officer of Bancshares and the Bank for a number years and in that capacity has gained unique and important knowledge about the operations, strategies and business prospects of Bancshares and the Bank, which knowledge Bancshares desires to continue to obtain the benefit of by engaging Consultant as a consultant hereunder, an engagement that the Consultant desires to accept; and

WHEREAS, the parties desire to set forth their agreements pertaining to Bancshares’ engagement of the Consultant.

NOW, THEREFORE, in consideration of the mutual promises, covenants and agreements contained in this Agreement, the parties agree as follows:

(a) Consultant shall retire from and resign as an employee of, and from all officer positions other than Chairman of the Board with, Bancshares and the Bank effective as of May 31, 2004 (the “Employment Termination Date”). Effective as of the Employment Termination Date, the Employment Agreement shall be terminated except for the provisions thereof which, by their terms, are intended to survive such termination. Effective as of the Effective Date, Bancshares does engage Consultant as a consultant pursuant to the terms of this Agreement, and Consultant agrees to accept such engagement as of the Effective Date.

(b) The term of this Agreement (the “Consulting Term”) shall be the period beginning on the Effective Date and ending on December 31, 2006, unless sooner terminated by Consultant in accordance with Section 6 hereof.

(a) The Consultant shall make himself available at reasonable times to consult with Bancshares and the Bank solely through the Chief Executive Officer, or those individuals designated by the Chief Executive Officer concerning matters pertaining to the development and implementation of the Bank’s and Bancshares’ business strategies and leadership development as may be specifically requested from time to time. To the greatest extent possible, Bancshares and Consultant shall schedule the requested occasions for consultation at least thirty (30) days in advance. Such consulting services shall include, without limitation, the following:

(i) identification and evaluation of potential growth opportunities, markets and acquisition candidates;

(ii) review of, and providing recommendations relating to, business development opportunities;

(iii) providing leadership development training and services for the officers and employees of Bancshares and the Bank which shall include, without limitation, the design and delivery of training courses and seminars;

(iv) personalized consulting and mentoring to the executive officers of Bancshares and the Bank;

(v) attendance at mutually agreed upon internal Bancshares and Bank meetings and meetings with third parties; and

(vi) such other tasks relating to the foregoing as may be designated in writing by Bancshares’ Chief Executive Officer.

(b) Bancshares understands that the Consultant shall, subject to the terms stated herein, be engaged in other business activities during the Consulting Term including, without limitation, his continued involvement with Chrysalis Partners, L.L.P. (“Chrysalis”) which includes consulting, coaching, teaching courses, publishing books and other activities related to Chrysalis. Furthermore, Consultant shall have the right to participate in the following activities so long as they do not conflict with the Consultant’s performance of his duties hereunder (i) engaging in and managing personal investments and other business activities, and (ii) serving on civic, religious, educational and/or charitable boards or committees. Accordingly, Bancshares agrees that Consultant shall not be required to devote all of his business efforts to the consulting services described above. Notwithstanding the foregoing, it is expected that Consultant shall provide, at Bancshares’ request, up to forty (40) hours of consulting services per month during the Consulting Term.

(c) Consultant shall be required to provide, at his own cost and expense, office space, office supplies, computer and related software and hardware, and such other equipment as may be required by Consultant to provide services hereunder; provided, however, Bancshares shall (i) reimburse Consultant for the actual cost of office rental

2

(inclusive of common area maintenance charges) in an amount not to exceed $3,300 per month during the Consulting Term, and (ii) shall sell and convey to Consultant the personal computer currently utilized by Consultant in his employment by Bancshares and the Bank at a mutually agreed upon price.

(d) During the Consulting Term and for so long as she continues to be employed by the Bank, the Bank shall make available to Consultant the services of his current Administrative Assistant, Diana Schmitt (“Schmitt”). For so long as she remains employed by the Bank, Schmitt shall remain on payroll of the Bank and shall continue to be eligible to receive benefits as may be available under the terms of the Bank’s benefit programs. Consultant shall reimburse the Bank for an amount equal to fifty percent (50%) of Schmitt’s salary and benefits, such reimbursement to be deducted from the compensation otherwise payable to Consultant pursuant to Section 3(a) below.

(e) It is possible that one or more employees of Bancshares or the Bank may participate in the consulting services, programs or seminars provided by Consultant. The parties agree that for the purposes of obtaining the best results from all consulting work, all Bancshares and Bank employee participation in programs or seminars provided or sponsored by Consultant shall be voluntary and not mandatory. Therefore, Bancshares acknowledges that all employees of Bancshares and the Bank that participate in the consulting sessions, if any, shall do so voluntarily and not as a result of coercion, pressure, a condition of employment or to satisfy anyone other than the individual employee. Bancshares acknowledges that Bancshares has been informed by Consultant that in order for individual employees to receive the intended results of the consulting services, their individual participation must be voluntary, free of any type of coercion, and the expression of their own individual free choice.

3. Compensation. Subject to the terms of this Agreement, during the Consulting Term Bancshares shall compensate Consultant as follows:

(a) Consultant shall be entitled to receive, and Bancshares shall pay, the following: (i) a base consulting fee of $250,000 per year, payable in equal monthly installments on or before the 1^st day of each month during the Consulting Term, and (ii) at the discretion of the Chief Executive Officer and subject to the approval of the appropriate committee of Bancshares’ board of directors, an annual bonus in an amount not to exceed $75,000, such annual bonus to be payable on or before February 28 of the year following the calendar year to which such bonus is attributable. Bancshares shall have no obligation to withhold any taxes that may be due from Consultant with respect to such consulting fees, and Consultant agrees to comply with all reporting and payment obligations imposed on him as an independent contractor pursuant to federal, state or local laws. Bancshares shall have no liability for taxes of whatever nature, including but not limited to, Federal income taxes, FICA taxes, Workers’ Compensation, or Social Security taxes. If Bancshares is required to pay or withhold any taxes or make any other payment with respect to fees payable to Consultant, Consultant will reimburse Bancshares in full for such taxes or amounts paid on demand or Bancshares may offset such amounts necessary from compensation due Consultant.

3

(b) During the Consulting Term and for so long as such may be provided by Bancshares or its subsidiaries pursuant to COBRA, Consultant shall be provided medical insurance coverage by Bancshares or the Bank through the COBRA provisions of the applicable medical insurance plan then in effect. Consultant shall pay an amount equal to the premium that Consultant would pay if Consultant were employed by Bancshares and Bancshares shall pay the remaining portion of the premiums associated therewith. Upon termination of COBRA benefits and for the remainder of the Consulting Term, Bancshares shall reimburse Consultant for comparable medical insurance coverage. Subject to the foregoing, Bancshares shall not be required to provide, and the Consultant shall not be entitled to receive, any benefits otherwise provided by Bancshares or the Bank to their employees.

(c) Subject to the provisions of Article 2 above, Bancshares shall reimburse Consultant for any and all business expenses reasonably necessary and incurred by Consultant in connection with providing the consulting services required hereunder. Prior to payment, Consultant shall submit to the Chief Executive Officer with each reimbursement claim adequate documentation satisfactory to the Chief Executive Officer to support such claim, including but not limited to actual bills, receipts or other evidence of expenditures. All such claims for reimbursement shall be submitted within 90 days of being incurred or forever waived.

4. Further Agreements of Consultant and Bancshares. The parties agree that nothing herein shall be construed as a limitation on Consultant to provide services to such other clients as Consultant may from time to time have the opportunity to provide services to; provided, however, that (i) the Consultant shall continue to be bound by the provisions of Article 5 of the Employment Agreement in accordance with the terms and provisions thereof, and (ii) Consultant further agrees, for and in consideration of amounts payable to Consultant hereunder and continued disclosure of confidential information by Bancshares and the Bank to Consultant, that during the Consulting Term and for a period of two years after termination of this Agreement, Consultant shall not provide consulting services of any nature to, or be employed by, any financial institution that either accepts deposits or extends credit of any type to its customers, operating in Texas. Consultant acknowledges that if he violates or threatens to violate this Section 4, Bancshares is entitled, in addition to any other rights available under Employment Agreement, to obtain a temporary restraining order and/or a preliminary and permanent injunction in addition to all other available remedies from a court, enjoining Consultant from violating this Agreement, in order to prevent immediate and irreparable harm to Bancshares and/or the Bank. Consultant further agrees that Bancshares shall be entitled to recover all of its expenses in connection with the enforcement of the provisions of this Section 4 including costs and attorneys’ fees.

Consultant further agrees that if any part of this Agreement is held to be unenforceable for any reason, then the covenants contained in this Agreement shall be interpreted in a manner that will render them enforceable. Consultant agrees that the restrictions contained in this Section are reasonable and acceptable to him.

4

5. Confidentiality.

(a) In the Consultant’s positions with Bancshares and the Bank, Bancshares and the Bank have previously (i) disclosed to Consultant, and placed Consultant in a position to have access to or develop, trade secrets or confidential information of Bancshares, the Bank and their affiliates, (ii) entrusted Consultant with business opportunities of Bancshares, the Bank and their affiliates, and/or (iii) placed Consultant in a position to develop goodwill on behalf of Bancshares, the Bank and their affiliates. Consultant acknowledges that in his director positions with Bancshares and the Bank and in the performance of his duties under this Agreement, Bancshares and the Bank shall continue to (i) disclose to Consultant, or place Consultant in a position to have access to or develop, additional and subsequent trade secrets or confidential information of Bancshares, the Bank and their affiliates, (ii) entrust Consultant with future business opportunities of Bancshares, the Bank and their affiliates, and/or (iii) place Consultant in a position to develop business goodwill on behalf of Bancshares, the Bank and their affiliates. Consultant recognizes and acknowledges that Consultant has had, and will continue to have, access to certain information of Bancshares and the Bank and that such information is confidential and constitutes valuable, special and unique property of Bancshares and the Bank. Consultant shall not at any time, either during or subsequent to the Consulting Term, disclose to others, use, copy or permit to be copied, except in pursuance of Consultant’s duties for and on behalf of Bancshares, the Bank, their affiliates and their respective successors, assigns or nominees, any Bancshares Confidential Information of the Bank or Bancshares (regardless of whether developed by Consultant) without the prior written consent of the Bank and Bancshares. The term “Bancshares Confidential Information” means any secret or confidential information or know-how and shall include, but shall not be limited to, the plans, customers, costs, prices, uses, corporate opportunities, proposed or contemplated acquisitions, research, financial data, evaluations, prospects, and applications of products and services, results of investigations or studies owned or used by Bancshares or the Bank, and all apparatus, products, processes, compositions, samples, formulas, computer programs, computer hardware designs, computer firmware designs, and servicing, marketing or manufacturing methods and techniques at any time used, developed, investigated, made or sold by Bancshares or the Bank, before or during the Consulting Term, that are not readily available to the public or that are maintained as confidential by Bancshares or the Bank. Consultant shall maintain in confidence any confidential information of third parties received as a result of the performance of his services hereunder in accordance with the obligations of Bancshares and/or Bank to such third parties and the policies established by Bancshares and the Bank. Consultant’s obligations under this Section 5(a) shall survive termination of this Agreement.

(b) Bancshares recognizes and acknowledges that in the course and scope of any requested consulting or training work by Consultant, Bancshares will have access to and gain information and knowledge relating to Consultant’s processes, products and business operations, including information relating to research, development, production and marketing of such consulting services (collectively, the “Consultant Confidential Information”). Bancshares further acknowledges that the maintenance of the proprietary nature of such information is essential to the business interests of the Consultant. Bancshares agrees that such Consultant Confidential Information presented during the Consulting Term,

5

either orally or in writing, is the sole property of the Consultant, and neither Bancshares, the Bank nor their affiliates shall reproduce, copy, duplicate, resell, or modify and resell such Consultant Confidential Information as a part of any course, training program, workshop or consulting business or any similar business activity for the purpose of receiving directly or indirectly any financial gain. The obligations of Bancshares, the Bank and their respective affiliates under this Section 5(b) shall survive the termination of this Agreement.

(c) In the event either party hereto becomes legally compelled (by oral questions, interrogatories, requests for information or documents, subpoena, civil investigative demand, regulatory demand or other similar process) to disclose any Confidential Information of the disclosing party, such party will provide the disclosing party with prompt written notice so that the disclosing party may seek a protective order or other appropriate remedy and/or waive compliance with the provisions of this Section 5. In the event that a protective order or other remedy is not obtained, or the disclosing party waives compliance with the provisions of this Section 5(c), such party will furnish only that portion of the Confidential Information which is legally required and exercise reasonable best efforts to obtain assurances that confidential treatment will be accorded the Confidential Information.

6. Termination.

(a) By Consultant. Consultant may terminate this Agreement for any reason without cause at any time during the Consulting Term by giving Bancshares at least ninety (90) days written notice. In the event Consultant terminates his Agreement hereunder, Bancshares’ sole and exclusive liability shall be to pay Consultant his pro rata portion of the compensation payable hereunder for services provided through date of termination and to pay any unreimbursed expenses to which Consultant is entitled hereunder. Bancshares shall have no other obligations to Consultant.

(b) Death or Disability of Consultant. Upon the death or disability of Consultant at any time during the Consulting Term, Bancshares shall continue to make all payments of the consulting fees due hereunder to the Consultant or the Consultant’s estate which shall include, without limitation, the Consultant’s executor, administrator or similar personal representative.

(c) Expiration of Consulting Term. Unless sooner terminated in accordance with the provisions of this Section 6, this Agreement shall be terminated upon the expiration of the Consulting Term in which event Bancshares shall pay to the Consultant amounts already due and owing for services rendered prior to the termination of the Consulting Term and any amounts due and owing for unreimbursed expenses for which Consultant is entitled hereunder.

(d) Continued Effectiveness. Notwithstanding the termination of this Agreement pursuant to this Section 6, the terms and provisions of this Agreement which are intended to survive the termination hereof shall continue to be enforceable against the Consultant.

6

7. Consultant an Independent Contractor. Consultant will furnish Consultant’s services as an independent contractor and not as an employee or agent of Bancshares, the Bank or of any company affiliated with either Bancshares or the Bank. Consultant agrees to conduct services hereunder in accordance with all applicable laws. Consultant has no power or authority to enter into any agreement or create any obligation, express or implied, on behalf of either Bancshares or the Bank, or to act for, represent, or bind either Bancshares or the Bank or any company affiliated with Bancshares in any manner. Unless otherwise provided herein, Consultant is not entitled to any medical coverage, life insurance, participation in either Bancshares’ or the Bank’s retirement or savings plan, vacation, incentive compensation or bonus plans, or other benefits afforded to the regular employees of either Bancshares or the Bank.

8. Indemnification.

(a) Consultant shall defend, indemnify and hold Bancshares and the Bank harmless from and against any loss, cost, damage, or liability for bodily injury to or death of any person, including Consultant, or damage to or destruction of any property, arising from or in connection with the rendering of the consulting services provided hereunder; provided, however, that Consultant shall have no obligation or liability with respect to any loss, cost, damage, or liability arising from or attributable to the willful misconduct or gross negligence of Bancshares, the Bank, their affiliates or their respective employees.

(b) Bancshares shall defend, indemnify and hold Consultant harmless from and against any loss, cost, damage or liability for bodily injury to or death of any person, or damage to or destruction of any property, arising from or in connection with the acts or omissions of Bancshares, the Bank, their respective employees pursuant to the terms of this Agreement or in any way connected with the rendering of the consulting services provided hereunder; provided, however, that Bancshares shall have no obligation or liability with respect to any loss, cost, damage, or liability arising from or attributable to the willful misconduct or gross negligence of Consultant, his agents or employees. The provisions of this Section 8 shall survive the termination of this Agreement.

9. Trademarks/Trade Names. Consultant acknowledges Bancshares’ and Bank’s sole ownership of all of the respective trademarks and trade names used by each entity. In his capacity as a consultant hereunder, Consultant shall have no authority to use trade names or trademarks, except as specifically authorized in writing in advance by Bancshares through its Chief Executive Officer. Except as may be necessary and appropriate for his actions as a director of the Bank and Bancshares, Consultant shall have no authority to use Bancshares’ or Bank’s trade names or trademarks on stationery, invoices, product literature, brochures, business cards, advertising or in any other materials of Consultant. Except as may be necessary and appropriate for his actions as a director of the Bank and Bancshares, Consultant shall not use Bancshares’ or Bank’s trade name or trademarks in any written communications with third parties without the prior written consent of the Chief Executive Officer. Notwithstanding the foregoing, the Consultant shall be permitted, without the prior consent of Bancshares, to (i) include in any resume or other biographical information statements reflecting his prior employment by, and services to, Bancshares and the Bank, and (ii) identify Bancshares and the Bank as clients of the Consultant in any advertising and promotional literature of the Consultant.

7

10. Governing Law. This Agreement shall be governed by the laws of the State of Texas, excluding its conflicts of law provisions.

11. Enforceability. Any invalidity, in whole or in part, of any provision of this Agreement shall not affect the validity of any other of its provisions.

12. Enforcement of Agreement. If either party brings an action to enforce its rights under this Agreement and prevails, it shall be entitled to recover its costs and expenses, including court costs and reasonable attorneys’ fees, if any, incurred in connection with such suit.

13. Sole Agreement. Except for such provisions of the Employment Agreement which continue to be binding upon Consultant following the Employment Termination Date, this Agreement represents the sole and entire agreement between the parties with respect to the subject matter hereof and supersedes any and all prior agreements, negotiations and discussions between the parties hereto with respect to the subject matters covered hereby.

14. Amendment to Agreement. Any amendment to this Agreement must be in writing signed by duly authorized representatives of the parties hereto and stating the intent of the parties to amend this Agreement.

15. Assignment. This Agreement, and his rights, duties and obligations hereunder, may not be assigned or otherwise transferred by the Consultant. The Consultant shall not assign or subcontract, in whole or in part, its obligations under this Agreement to provide consulting services without Bancshares’ prior consent. No such approval shall relieve the Consultant from any of his obligations or liabilities under this Agreement.

16. Notice. All notices, requests, demands and other communications required or permitted under this Agreement shall be deemed to have been duly given and made if in writing and served either by personal delivery or mail, postage prepaid, registered or certified mail, return receipt requested, in the U.S. mail to the party for whom it is intended or one business day after having been dispatched by an overnight courier service bearing the address set forth in this Agreement with respect to Bancshares and with respect to Consultant, such address as may be designated in writing by the Consultant:

17. Bancshares’ Successors and Assigns. This Agreement shall be binding upon, and inure to the benefit of, Bancshares and its successors and assigns and upon any person acquiring, whether by merger, consolidation, purchase of assets or otherwise, all or substantially all of Bancshares’ assets and business.

18. Counterparts to Agreement. This Agreement may be executed in counterparts, all of which, when taken together, shall constitute one agreement, with the same force and effect as if all signatures had been entered on one document.

8

IN WITNESS WHEREOF, the parties hereto have executed this Agreement on the 9th day of June, 2004, to be effective as of the Effective Date.

9