VOLUNTARY SEPARATION AND RELEASE AGREEMENT

Exhibit 10.1

VOLUNTARY SEPARATION AND RELEASE

AGREEMENT

This Voluntary Separation and Release Agreement (Agreement) is entered into by and between Sterling Bancshares, Inc. and Sterling Bank (severally and collectively, “Company”) and Sonny Lyles, in his individual capacity, (Lyles). As used in this Agreement, Company shall include and encompass all entities related to the Company including Sterling Bank and any other affiliated or related entities including without limitation all of the past, present or future owners, affiliated, related and/or subsidiary entities of the Company, any successor or predecessor in interest to the operations or business of the Company, and all past, present or future directors, officers, employees, agents, attorneys and representatives of the Company and its owners.

PREAMBLE

Lyles has expressed his desire to retire as an officer and employee of the Company and does hereby retire effective at the end of the business day on December 31, 2009, (the Retirement Date). The Company has offered Lyles certain benefits as outlined in this Agreement to which Lyles is not already entitled as consideration for Lyles’s agreements outlined herein. In recognition of Lyles’s service to the Company, and in response to his stated desire to retire, the parties state the following Agreement.

AGREEMENT

In consideration of the mutual promises and undertakings of the parties, the sufficiency of which is recognized and accepted by each of the parties, it is agreed as follows:

1 . Voluntary Resignation. Lyles shall voluntarily retire and does hereby resign as an officer, executive, and employee of the Company and as a board member of Sterling Bank effective December 31, 2009. Lyles will not conduct any business on behalf of the Company, perform any duties for the Company or come to the offices of the Company after December 31, 2009, except to conduct personal banking business as a bank customer or by prior mutual agreement with the Company’s Chief Executive Officer (CEO) J. Downey Bridgwater or his designee. Lyles will remain an employee of the Company through December 31, 2009.

2. Non-Competition Agreement. The Company agrees to release Lyles from certain specific provisions contained in Lyles’ Severance and Non-Competition Agreement dated May 2, 2005. The specific provisions from which Lyles is released are:

a. The prohibition on directly or indirectly, owning, managing, operating, controlling, investing or acquiring an equity interest in any financial institution (or any affiliate thereof including, without limitation, any bank holding company or financial holding company) with $10 billion or less in assets located or conducting business in Harris County, Texas or any of its contiguous counties (the “Territory”) which competes with the business conducted by any Sterling Entity; and

b. The prohibition on engaging in or carrying on, either directly or indirectly, whether for himself or as an employee, officer, director, agent, consultant, proprietor,

1

partner, stockholder, member, joint venturer, investor, or other paid participant, any business with, on behalf of or as a financial institution within the Territory which competes with the business conducted by any Sterling Entity.

3. Other Benefits. As of the Retirement Date, Lyles shall also receive from the Company:

a. Health Insurance Coverage. Subject to COBRA regulations, Lyles may continue his health insurance coverage after the Retirement Date as provided under COBRA.

b. Vacation. On the December 31, 2009 payroll date, Lyles shall be paid for any accrued, unused vacation as of the Retirement Date.

c. Technology/Communications. Lyles shall retain Company-owned property provided to him for business, such as his lap top computer and his cellular telephone. Prior to the end of business day on December 31, 2009, the Technology Department will remove any bank files and/or bank software from Lyle’s computer. Lyles shall be entitled to retain his cellular telephone number.

d. Employee Saving Plan. Lyles may leave his vested balance in his Schwab 401(k) account and continue to direct the investments to his funds and participate in any gains or losses for his investments.

e. Equity Awards. Lyles shall have thirty (30) days following the Retirement Date to exercise any vested portion of his stock options.

f. References. The Company’s policy of neutral reference will be applicable.

4. Total Benefits. Lyles agrees that the benefits described in this Agreement are in lieu of any other benefits of any type to which he might otherwise be entitled.

5. Restrictive Covenants In consideration of the promises, recitals and covenants set forth herein, Lyles agrees as follows:

a. Nonsolicitation of Employees. For twelve months following the Retirement Date, Lyles agrees that he will not, directly or indirectly, attempt to hire, contact or solicit any of the employees of the Company for the purpose of inducing such individuals to terminate their employment with the Company.

b. Nonsolicitation of Vendors, Customers and Suppliers. For twelve months following the Retirement Date, Lyles agrees that he will not on his own behalf or on behalf of others, either directly or indirectly, call upon, solicit, divert or take any customers, clients, vendors or suppliers of the Company, who were the customers, clients, vendors or suppliers of the Company during Lyles’s employment with the Company, for the purpose of interfering or competing with the Company’s existing business relationships with such customers, clients, vendors or suppliers.

2

c. Nondisclosure of Confidential Information.

(1) Lyles agrees that any confidential or proprietary business information or trade secret information (herein referred to collectively as “Confidential Information”) of the Company gained by Lyles during his employment with the Company which is not generally known to others in the relevant trade or industry and which Lyles has obtained knowledge of as a result of his employment with the Company, whether relating to methods, processes, techniques, inventions, discoveries, lists of sales, customers and suppliers or other marketing information, as well as improvements thereof or know-how relating thereto, shall be secret and confidential and shall not be used or disclosed by him to third parties unrelated to the Company, except as the Company’s CEO may otherwise authorize in writing.

(2) Lyles agrees that any Confidential Information of any customer, person, firm or corporation with which the Company may do business, not generally known to others in the relevant trade or industry and which Lyles has obtained knowledge of as a result of his employment with the Company, whether relating to methods, processes, techniques, inventions, discoveries, lists of accounts or loans, customers and suppliers or other marketing information, as well as improvements thereof or know-how relating thereto, shall be secret and confidential and shall not be used or disclosed by him.

(3) Lyles agrees to deliver to the Company on the Retirement Date or before all copies of the Confidential Information of the Company, any and all materials developed by the Company for use in its business and any and all other property whatsoever belonging to the Company or any customer of the Company which is in the possession of Lyles.

(4) Lyles’s agreement herein regarding the Confidential Information of the Company shall be in addition to Lyles’s preexisting obligations under the common law or other agreements between the Company and Lyles.

6. Release.

a. In consideration of the various recitals and covenants recited in this Agreement, including but not limited to the benefits described in paragraphs 2 and 3, Lyles does hereby and forever: (i) release and discharge the Company and all of its affiliated, parent and subsidiary entities, and its and their owners, officers, directors, employees, agents, attorneys and representatives (collectively “Released Parties”) from and against any and all claims, demands, damages and causes of action, whether known or unknown, if any, of every type and character, whether at law, in equity or administrative that Lyles may have, does have or hereafter acquires against any or all of the Released Parties arising out of or in any way pertaining to, in whole or in part, his employment with the Company including, but not limited to the Severance and Non-Competition Agreement dated May 2, 2005, and the resignation of such employment, attributable to the time period prior to and including the effective date hereof, and (ii) waive any

3

and all claims, demands, damages, and causes of action against the Released Parties, whether known or unknown, if any, of every type and character, whether at law, in equity or administrative that Lyles may have, does have or hereafter acquires arising out of or in any way pertaining to, in whole or in part, his employment with the Company and the resignation of such employment, against any or all of the Released Parties attributable to the time period prior to and including the effective date hereof. This Agreement does not waive rights or claims that may arise after the date the Agreement is executed.

b. The release, discharge and waiver set forth above is intended to be as broad as is permissible under applicable law and is to include, but not be limited to, any claim, demand, damage and cause of action arising out of or pertaining to (i) employment discrimination or retaliation of any kind, (ii) re-employment with the Company or any of its parent, subsidiary, affiliated, or successor entities, (iii) Title VII of the Civil Rights Act of 1964, as amended, (iv) the Americans with Disabilities Act, as amended, (v) the Age Discrimination in Employment Act of 1967, as amended, (ADEA) (vi) the Older Workers Benefit Protection Act, as amended, (OWBPA) (vii) the Texas Labor Code, as amended, (viii) breach of contract, tort, or personal injury of any type or character, (ix) any claim under any other foreign, federal, state or local law, rule or regulation, and (x) the Employee Retirement Security Act, as amended (ERISA); however, this waiver shall not apply to (a) any cause of action under ERISA relating to an employee benefit plan that is qualified under Section 401(a) of the Internal Revenue Code of 1986, as amended, or that is a medical or health care plan, or (b) any claims which Lyles may have against the Company for breach of the terms and conditions set forth in this Agreement. This release also does not waive any claims that the law clearly states may not be waived by agreement of the parties such as workers’ and unemployment compensation claims.

c. Lyles understands that following the seven-day revocation period stated below, this release will be final and binding. Lyles promises that he will not pursue any claim that he has settled by this release. If he breaks this promise, Lyles agrees to pay all of the Company’s costs and expenses (including reasonable attorneys’ fees) related to the defense of any claims except this promise not to sue does not apply to claims under the OWBPA and the ADEA. Although Lyles is releasing claims that he may have under the OWBPA and ADEA, Lyles understands that he may challenge the knowing and voluntary nature of this release before a court, the Equal Employment Opportunity Commission (EEOC), or any other federal, state or local agency charged with the enforcement of any employment laws. Lyles also understands that nothing in this release prevents him from filing a charge or complaint with or from participating in an investigation or proceeding conducted by the EEOC or any other federal, state or local agency charged with the enforcement of any employment laws. Lyles understands, however, that if he pursues a claim against the Company under the OWBPA and/or the ADEA to challenge the validity of this release and prevails on the merits of an ADEA claim, a court has the discretion to determine whether the Company is entitled to restitution, recoupment, or set off (hereinafter “reduction”) against a monetary award obtained by him in the court proceeding. Lyles also recognizes that the Company may be entitled to recover costs and attorneys fees incurred by the Company as specifically authorized under applicable law.

7. Nondisparagement. Lyles will not make any comments to the employees, vendors, customers, suppliers of the Company or to the press or to others with the intent to

4

impugn, castigate or otherwise damage the reputation of the Company or any of the owners, directors, officers, or employees of the Company. The present officers, members of the Company will not make any comments to the employees, vendors, customers, suppliers of the Company or to the press or to others with the intent to impugn, castigate or otherwise damage the reputation of Lyles.

8. Nondisclosure. Lyles agrees that he will not make any public announcement or statement or otherwise discuss or disclose the terms of this Agreement with or to any past or present employees, agents or representatives of the Company (subject to those Company employees who have a business need to know) or to any third party, including without limitation, the press, vendors or customers. However, it is understood that Lyles may communicate regarding this Agreement with his financial and legal advisers, family members, and others with a valid need to know, with the understanding that disclosures to such individuals shall be made to them with an explanation by Lyles of the confidential nature of this Agreement and the expressed understanding of such nondisclosure and confidentiality obligations by the receiving party.

9. Cooperation in Legal Proceedings. Lyles agrees that he will cooperate with the Company in providing information, including testimony at trial or in depositions, if needed, regarding any present claims or future claims filed against the Company which are based on factual allegations about which Lyles has knowledge.

10. Retirement. Lyles agrees to tender any letters of retirement effective on the Retirement Date, which the Company may reasonably request, to effectively resign from any and all positions Lyles presently holds within the Company or on behalf of the Company.

11. Presentation Advisory. The Company presented Lyles with this Agreement for execution on or after January 1, 2010, but not later than January 31, 2010. Lyles expressly acknowledges that he has been offered and given at least 21 calendar days in which to consider and review this Agreement prior to signing it, that such time has been sufficient to permit him to review its terms. Lyles expressly acknowledges that prior to executing this Agreement he was and is by this Agreement advised to consult with legal counsel of his choice concerning the terms of this Agreement. Lyles specifically acknowledges that he fully and completely understands the terms of this Agreement and their significance, that he accepts such terms and enters into the Agreement freely and voluntarily.

12. Effective Date. Subject to the last sentence of this paragraph, this Agreement shall become effective: eight (8) calendar days after the date this Agreement is signed by Lyles, as evidenced by the date adjacent to the signature of Lyles at the end of this Agreement. Such signed Agreement is to be transmitted to Wanda Dalton on the date of signing. This Agreement shall not be effective and shall be deemed null and void as if never made if, prior to the Effective Date, Lyles revokes his earlier acceptance of this Agreement. Any revocation must be in writing and delivered into the possession of Wanda Dalton. This Agreement shall become final and binding on the eighth (8^th) day after Lyles signs the Agreement, unless it is revoked pursuant to the terms of this paragraph.

5

13. Agreement Construction. It is agreed and understood that this Agreement contains the entire understanding of the parties and that, with the exception of various plan documents pertaining to the various benefit plans referenced throughout this Agreement, there are no additional or other promises, representations, terms or provisions applicable to the parties other than those expressly contained herein, and that all prior negotiations and agreements are merged and integrated into this Agreement. Except to the extent preempted by federal law, Texas law shall be applicable to this Agreement. This Agreement shall not be modified except in writing by each of the parties, which writing shall specifically reference this Agreement. If any part of this Agreement is found invalid or unenforceable, the remainder of the Agreement shall not be affected.

14. Counterparts. This Agreement may be executed in one or more counterparts, each of which shall be considered as an original, and both of which shall constitute one and the same agreement.

IN WITNESS OF WHICH, the parties have executed this Agreement on the date set forth below.

SWORN TO AND SUBSCRIBED before me on this 1^st day of January, 2010.

SWORN TO AND SUBSCRIBED before me on this 31^st day of December, 2009.

6