SEVERANCE AND RELEASE AGREEMENT

Exhibit 10.1

SEVERANCE AND RELEASE AGREEMENT

WHEREAS, Sterling Bancshares, Inc., a Texas Corporation (“Bancshares”), Sterling Bank, a banking association chartered by the State of Texas and an indirect subsidiary of Bancshares (“Bank”), collectively (the “Company”), and John A Rossitto (“Executive”) previously entered into a Severance and Non-Competition Agreement dated January 11, 2006 (“Prior Agreement”);

WHEREAS, Executive ceased to be Company’s Executive Vice President of Retail Banking effective July 1, 2009; and

WHEREAS, Executive shall retire as the Company’s Vice Chairman, effective October 5, 2009; and

WHEREAS, Executive and the Company agree that his retirement with the Company is the result of a mutual agreement between the two parties.

NOW, THEREFORE, effective as of the date executed below (“Effective Date”), Executive and the Company hereby agree to enter into this Severance and Release Agreement (“Agreement”) setting forth their respective obligations related to Executive’s separation from the Company as follows:

1. Severance from Employment. Executive shall resign as Vice Chairman of the Company and as any other officer, director, manager or similar functionary of all entities related to the Company, effective October 5, 2009.

2. Severance Payments. The Company shall pay and provide, in exchange for the execution of this Agreement, the Executive with the following:

(a) Two (2) years’ base pay payable in equal installments each regular pay period during the two (2) years beginning with the first regular payroll date following the Effective Date, with the initial payment to occur, or be credited, on October 15, 2009. For purposes of this calculation, base pay shall be calculated based on the rate of annual salary being paid by the Company to Executive as of September 30, 2009. Because Executive is a “specified employee,” as such term is defined within the meaning of Section 409A of the Internal Revenue Code of 1986, as amended (“Code Section 409A”), payment of all amounts under this Section (a) shall be suspended for a period of six (6) months and one (1) day immediately following the Effective Date. Immediately thereafter, the Company shall pay to Executive all of the suspended payments under this Section (a), with interest accrued on such amounts at the prime rate (as published in the Wall Street Journal).

(b) Executive shall receive annual bonus payments, payable on the first and second anniversaries of the Effective Date, in an amount equal to fifty thousand dollars ($50,000).

(c) Reimbursement for the use of a cell phone in an amount comparable to the cell phone provided by the Company on the Effective Date for the two (2) years following the Effective Date;

1

(d) Continued participation in the Company’s group health, dental, and/or vision plan (“Health Plan”) during the two (2) year period following October 31, 2009. This coverage shall be provided as follows:

(i) During the initial eighteen (18) months immediately following October 31, 2009 each of Executive, his spouse and his covered dependents may enroll in COBRA as permitted under the Health Plan. If one or more of such individuals elect to enroll in COBRA, then Executive shall pay an amount equal to the subsidized cost of coverage paid by an active employee of the Company to receive such coverage.

(ii) During the period between May 1, 2011, and October 31, 2011, each of Executive, his spouse and his covered dependents may participate in the Health Plan by paying the full non-subsidized cost to receive such coverage.

Nothing in this Section (d) shall be interpreted as limiting the right of Executive’s spouse and covered dependents to receive extended participation in the Company’s group health plan under COBRA in the event Executive elects to enroll in Medicare in a timely manner.

(e) Continued life insurance benefits from the Company during the two (2) year period following the Effective Date at a level of coverage that is equal to the coverage level provided to the Executive on September 30, 2009;

(f) Club dues paid for the two (2) years following the Effective Date that are equal to than those provided to the Executive immediately prior to the Effective Date;

(g) Continuation of banking services without service charge or at a reduced charge for the two (2) years following the Effective Date if any of these banking products were being utilized by the Executive immediately prior to his resignation;

(h) Payment of reasonable and customary business related expenses incurred through the last day of active employment, provided all receipts shall be submitted in writing to the Company within ninety (90) days following the Effective Date;

(i) Outplacement or executive search firm consulting services during the two (2) year period following the Effective Date, provided the total value of such services shall not exceed $20,000;

(j) Executive will be permitted to exercise the vested portion of his stock options during the ninety (90) day period immediately following the Effective Date. Executive agrees that the only vested stock option awards to which he is entitled are those listed on the attached Exhibit A.

(k) In the event that Executive (or his spouse or dependents) is enrolled in the Health Plan during the period designated in Section (d)(ii) above, the Company shall reimburse Executive for a portion of the medical premium expenses that he incurs to purchase such continued medical coverage under the Health Plan, but only to the extent such expense is equal to the premium level that would be paid by an employee of the Company receiving the same level of coverage (which amount shall be referred to herein

2

as the “Medical Reimbursement”). In addition, the Company will pay Executive an amount equal to the aggregate of the Federal, state and local income taxes that Employee pays on the Medical Reimbursement payments, plus the additional Federal, state and local income taxes imposed on Employee due to such additional income tax gross-up payment by the Company. The Company will pay the additional income tax gross-up amounts owed to Executive under this paragraph at the same time payments of the Medical Reimbursement are made.

The Company shall reimburse Executive for the expenses related to benefits provided under Subsections 2(f), (g), and (k) pursuant to Treasury Regulation Section 1.409A-3(i)(1)(iv)(A). The availability of reimbursement under this paragraph in any calendar year will not be increased or decreased to reflect the amount actually reimbursed in a prior or subsequent calendar year, and all reimbursements under this paragraph will be paid to Executive within twenty (20) days following the Company’s receipt of a request for reimbursement. The Executive shall not be permitted to exchange this right of reimbursement for cash or any other benefit.

3. Release of all Claims. In consideration for Sections 1 and 2 above, Executive voluntarily and knowingly waives, releases, and discharges the Company, its parent, predecessor, successor, subsidiary, and affiliate companies, and all of their executives, officers, directors, owners, agents and assigns from all claims, liabilities, demands, and causes of action, known or unknown, fixed or contingent, which Executive may have or claim to have against any of them as a result of Executive’s employment and/or severance from employment. Executive agrees not to file a lawsuit to assert any such released claims and Executive agrees not to accept any monetary damages or other personal relief (including legal or equitable relief) in connection with any administrative claim or lawsuit filed by any person or entity. This waiver, release and discharge includes, but is not limited to:

(a) Claims arising under federal, state, or local laws regarding employment or prohibiting employment discrimination such as, without limitation, Title VII of the Civil Rights Act of 1964, the Equal Pay Act, the Age Discrimination in Employment Act, the Older Workers’ Benefit Protection Act, the Genetic Information Nondiscrimination Act, the Occupational Health and Safety Act, the National Labor Relations Act, Section 1981 of the Civil Rights Act of 1866, the Americans with Disabilities Act, the Fair Labor Standards Act, the Family and Medical Leave Act (FMLA), Chapters 21, 61 and 451 of the Texas Labor Code, the Sarbanes Oxley Act of 2002, Comprehensive Omnibus Budget Reconciliation Act of 1985 (COBRA), the Worker Adjustment and Retraining Notification (WARN) Act,

(b) Claims for breach of oral or written express or implied contract or promissory estoppel or quantum meruit,

(c) Claims for personal injury, harm, or other damages (whether intentional or unintentional and whether occurring on the job or not, including, without limitation, negligence, defamation, misrepresentation, fraud, intentional infliction of emotional distress, assault, battery, invasion of privacy, and other such claims),

3

(d) Claims growing out of any legal restrictions on the Company’s right to terminate its executives including any claims based on any violation of public policy or retaliation for filing a workers’ compensation claim,

(e) Claims for workers compensation, wages or any other compensation other than any pending workers’ compensation benefits claim, or

(f) Claims for benefits including, without limitation, those arising under the Employee Retirement Income Security Act of 1974, as amended.

Nothing in this Agreement shall be construed as an attempt to waive any claim which is not waivable as a matter of law.

4. Release of Age Discrimination Claims. In addition, Executive acknowledges the following:

(a) that this Agreement is written in a manner calculated to be understood by Executive and that Executive in fact understands the terms, conditions and effect of this Agreement.

(b) This Agreement refers to rights or claims arising under the Age Discrimination in Employment Act and Older Workers’ Benefit Protection Act.

(c) Executive does not waive rights or claims that may arise after the date this Agreement is executed.

(d) Executive waives rights or claims only in exchange for consideration in addition to anything of value to which Executive is already entitled.

(e) Executive is advised to consult with an attorney prior to executing the Agreement.

(f) Executive has twenty-one (21) days in which to consider this Agreement before accepting, but need not take that long if the Executive does not wish to. Executive acknowledges that any decision to sign this Agreement before the twenty-one (21) days have expired has done so voluntarily and not because of any fraud or coercion or improper conduct by Employer.

(g) This Agreement allows a period of seven (7) days following execution/signing of the Agreement during which Executive may revoke this Agreement.

(h) Executive fully understands all of the terms of this waiver agreement and knowingly and voluntarily enters into this Agreement.

(i) Executive has been given this Agreement to consider on September 30, 2009 and any notice of acceptance or revocation should be made by Executive by hand delivery, mail, fax or email to Wanda Dalton, Sterling Bancshares, Inc., 10260 Westheimer Road, Houston, Texas 77042.

4

5. Administrative Complaint. This Agreement does not impose any restriction, condition precedent, any penalty or any other limitation on the right to file an administrative charge or complaint, or otherwise prevent the filing of any administrative complaint, including a challenge to the validity of this Agreement, with the Equal Employment Opportunity Commission (“EEOC”), or on the right to participate in an investigation or proceeding conducted by the EEOC or any comparable state agency. However, Executive understands and recognizes that even if a charge is filed by him or on his behalf with an administrative agency, he will not be entitled to any damages or payment of any money relating to any event which occurred prior to his execution of this Agreement.

6. Return of Employer Property. Executive agrees that he will immediately return to the Company all property (including property purchased or paid for by the Company in Executive’s possession, custody or control) which belongs to the Company, including any keys, access cards, computers, cell phones, pagers, or other equipment and any Company records, files, data, and documents (whether on a work or personal computer, in electronic format or otherwise, and whether confidential in nature or not). Executive shall immediately report to the Company any passwords for Executive’s computer or other access codes for anything associated with Executive’s employment with the Company.

7. Non-Disparagement. Executive agrees to not directly or indirectly engage in any conduct that will disparage, denigrate, or discredit the Company or any of its divisions, affiliates, parents, subsidiaries, or its owners, directors, officers, agents, current or former Executives, attorneys, or representatives.

8. Transition Services. Executive shall make himself available to the Company to provide transition services on a reasonable basis during the twelve (12) month period following the Effective Date. Executive shall provide such services as directed by the Company’s Chairman and shall be reimbursed for any reasonable out of pocket expenses associated with the provision of such services.

9. Neutral Reference. For reference inquiries directed to the Company’s Human Resources department, the Company shall provide a neutral reference regarding Executive’s employment, including Executive’s position and dates of employment. Bancshares and/or Bank is not responsible for references not directed to the Human Resources department.

10. Non-Disclosure of Confidential Information. Executive acknowledges that he has had access to confidential information (“Confidential Information”) while employed by the Company, including without limitation, information concerning the products, policies, practices, customers, pricing, costs, suppliers, methods, processes, techniques, finances, administration, executives, devices, trade secrets and operations of the Company. Executive acknowledges that this information is confidential, not known outside of the Company’s business, valuable, special and/or a unique asset of the Company. Executive agrees that in further consideration for the promises made in this Agreement, Executive will not disclose in any way to any person, or use for Executive’s own benefit or for the benefit of anyone else or any other person or entity, the Confidential Information described above which was gained while employed by the Company. This

5

prohibition includes not using any information learned about other executives while employed by the Company to divert those executives from the Company and not using any information learned about customers to divert those customers from the Company. These provisions do not limit or restrict any similar or related obligations that the Executive may have undertaken in other agreements with the Company or which apply to Executive under common law. Executive acknowledges that because damages may be difficult to calculate for a breach of these provisions, the Company may seek immediate injunctive relief to enforce these obligations, in addition to any legal or other relief to which the Company may be entitled.

11. Confidential Agreement. Executive understands and agrees not to discuss or disclose any of the terms of this Agreement with any person or entity except for Executive’s spouse, attorney, financial advisor, and government tax authorities or except as required by law. Executive agrees that any inquiries Executive has regarding this Agreement, his employment, benefits, or termination of employment should be directed to Wanda Dalton, Sterling Bancshares, Inc., 10260 Westheimer Road, Houston, Texas 77042.

12. No Admission. Executive understands this Agreement is not and shall not be deemed or construed to be an admission by the Company of any wrongdoing of any kind or of any breach of any contract, law, obligation, policy, or procedure of any kind or nature.

13. Entire Agreement. Executive has carefully read and fully understands all of the terms of this Agreement. Executive agrees that this Agreement sets forth the entire agreement between the Company and Executive regarding all issues except that it does not replace existing agreements (if any) regarding confidentiality, non-disclosure or non-solicitation issues. Any obligations under those agreements remain ongoing and in place in their entirety.

14. Representations; Modifications; Severability. Executive acknowledges that Executive has not relied upon any representations or statements, written or oral, not set forth in this Agreement. This Agreement cannot be modified except in writing and signed by both parties. If any part of this Agreement is found to be unenforceable by a court of competent jurisdiction, then such unenforceable portion will be severed from and shall have no effect upon the remaining portions of the Agreement. The Company may assign its rights and obligations under this Agreement.

15. Applicable Law. This Agreement shall be governed by and interpreted under the laws of the State of Texas without regard to Conflict of Laws. The parties agree that any dispute concerning this Agreement shall be brought only in a court of competent jurisdiction in Harris County, Houston, Texas.

16. Execution. This Agreement may be executed in multiple counterparts, each of which shall be deemed an original and all of which shall constitute one instrument.

6

AGREED AND ACCEPTED on this 19^th day of October, 2009.

BEFORE ME, the undersigned authority, on this day personally appeared John A. Rossitto, known to me to be the person whose name is subscribed above and acknowledged to me that he did execute the same for the purpose and consideration therein expressed.

GIVEN UNDER MY HAND AND SEAL OF OFFICE this 19th day of October, 2009.

[SEAL]

7

AGREED AND ACCEPTED on this 20^th day of October, 2009.

BEFORE ME, the undersigned authority, on this day personally appeared J. Downey Bridgwater, President and Chief Executive Officer of Sterling Bancshares, Inc., known to me to be the person whose name is subscribed above and acknowledged to me that he was authorized and did execute the same on behalf of Sterling Bancshares, Inc. for the purpose and consideration therein expressed.

GIVEN UNDER MY HAND AND SEAL OF OFFICE this 20th day of October, 2009.

[SEAL]

8

COBRA Continuation Coverage Premium Payments

(as of Effective Date of Agreement)

COBRA premium payments if Executive elects continuation coverage for himself and Family (Employee+Family):

Medical

Dental

Vision

If Executive elects not to enroll himself for COBRA continuation coverage, his dependents are eligible for continuation coverage at the following COBRA premium rates (Employee + Child):

Medical

Dental

Vision

9