Document:

<PAGE>

                                                                     EXHIBIT 4.5

                          FIRST SUPPLEMENTAL INDENTURE

                                    BETWEEN

                           STERLING BANCSHARES, INC.

                                      AND

                             BANKERS TRUST COMPANY,

                                   AS TRUSTEE

                          DATED AS OF MARCH 21, 2001.
<PAGE>

                               TABLE OF CONTENTS*
                                                                           PAGE
                                                                           ----
ARTICLE I DEFINITIONS......................................................  2
 Section 1.1  Definition of Terms..........................................  2

ARTICLE II GENERAL TERMS AND CONDITIONS OF THE DEBENTURES..................  4
 Section 2.1  Designation and Principal Amount.............................  4
 Section 2.2  Maturity.....................................................  4
 Section 2.3  Form and Payment.............................................  4
 Section 2.4  Global Debenture.............................................  5
 Section 2.5  Interest.....................................................  6

ARTICLE III PREPAYMENT OF THE DEBENTURES...................................  7
 Section 3.1  Special Event Prepayment.....................................  7
 Section 3.2  Optional Prepayment by Company...............................  8
 Section 3.3  No Sinking Fund..............................................  8

ARTICLE IV EXTENSION OF INTEREST PAYMENT PERIOD............................  8
 Section 4.1  Extension of Interest Payment Period.........................  8
 Section 4.2  Notice of Extension..........................................  9
 Section 4.3  Limitation of Transactions................................... 10

ARTICLE V CHANGE OF STATED MATURITY DATE................................... 10
 Section 5.1  Change of Stated Maturity Date............................... 10
 Section 5.2  Notice of Change of Stated Maturity Date..................... 10

ARTICLE VI EXPENSES........................................................ 11
 Section 6.1  Payment of Expenses.......................................... 11
 Section 6.2  Payment Upon Resignation or Removal.......................... 12

ARTICLE VII COVENANT TO LIST ON EXCHANGE................................... 12
 Section 7.1  Listing on an Exchange....................................... 12

ARTICLE VIII FORM OF DEBENTURE............................................. 13
 Section 8.1  Form of Debenture............................................ 13

ARTICLE IX ORIGINAL ISSUE OF DEBENTURES.................................... 13
 Section 9.1  Original Issue of Debentures................................. 13

ARTICLE X MISCELLANEOUS.................................................... 13
 Section 10.1 Ratification of Indenture.................................... 13
 Section 10.2 Trustee Not Responsible for Recitals......................... 13
 Section 10.3 Governing Law................................................ 13
 Section 10.4 Counterparts................................................. 14

 *THIS TABLE OF CONTENTS SHALL NOT, FOR ANY PURPOSE, BE DEEMED TO BE A PART OF
  THIS FIRST SUPPLEMENTAL INDENTURE.

                                       i
<PAGE>

                          FIRST SUPPLEMENTAL INDENTURE
                                    BETWEEN
                           STERLING BANCSHARES, INC.
                                      AND
                             BANKERS TRUST COMPANY

     FIRST SUPPLEMENTAL INDENTURE, dated as of March 21, 2001 (the "First
Supplemental Indenture"), between Sterling Bancshares, Inc., a Texas corporation
(the "Company"), and Bankers Trust Company, a New York banking corporation, as
trustee (the "Trustee") under the Indenture dated as of March 21, 2001 between
the Company and the Trustee (the "Indenture").

     WHEREAS, the Company executed and delivered the Indenture to the Trustee to
provide for the future issuance of the Company's unsecured junior subordinated
securities to be issued from time to time in one or more series as might be
determined by the Company under the Indenture, in an unlimited aggregate
principal amount which may be authenticated and delivered as provided in the
Indenture;

     WHEREAS, pursuant to the terms of the Indenture, the Company desires to
provide for the establishment of a new series of such securities to be known as
its 9.20% Junior Subordinated Deferrable Interest Debentures due March 21, 2031
(the "Debentures"), the form and substance of such Debentures and the terms,
provisions and conditions thereof to be set forth as provided in the Indenture
and this First Supplemental Indenture;

     WHEREAS, the Company and Sterling Capital Trust II, a Delaware statutory
business trust (the "Trust"), has offered to the public $28,750,000 aggregate
liquidation amount of its 9.20% Trust Preferred Securities (the "Preferred
Securities"), representing preferred undivided beneficial interests in the
assets of the Trust, and proposes to invest the proceeds from such offering,
together with the proceeds of the issuance and sale by the Trust to the Company
of $889,175 aggregate liquidation amount of its 9.20% Trust Common Securities
(the "Common Securities"), in $29,639,175 aggregate principal amount of the
Debentures; and

     WHEREAS, the Company has requested that the Trustee execute and deliver
this First Supplemental Indenture and all requirements necessary to make this
First Supplemental Indenture a valid instrument in accordance with its terms,
and to make the Debentures, when executed by the Company and authenticated and
delivered by the Trustee, the valid obligations of the Company, have been
performed, and the execution and delivery of this First Supplemental Indenture
has been duly authorized in all respects.

     NOW THEREFORE, in consideration of the purchase and acceptance of the
Debentures by the Holders thereof, and for the purpose of setting forth, as
provided in the Indenture, the form and substance of the Debentures and the
terms, provisions and conditions thereof, the Company covenants and agrees with
the Trustee as follows:
<PAGE>

                                   ARTICLE I

                                  DEFINITIONS

     Section 1.1  Definition of Terms.  Unless the context otherwise requires:

        (a)  a term defined in the Indenture has the same meaning when used in
this First Supplemental Indenture;

        (b)  a term defined anywhere in this First Supplemental Indenture has
the same meaning throughout;

        (c)  the singular includes the plural and vice versa;

        (d)  a reference to a Section or Article is to a Section or Article of
this First Supplemental Indenture;

        (e)  headings are for convenience of reference only and do not affect
interpretation;

        (f)  the following terms have the meanings given to them in the
Declaration:

             (i)  Administrative Trustee;

             (ii)  Delaware Trustee;

             (iii) Distributions;

             (iv) Preferred Securities Guarantee;

             (v)  Property Trustee; and

             (vi)  Underwriting Agreement.

        (g)  the following terms have the meanings given to them in this Section
1.1(g):

          "Additional Sums" shall have the meaning set forth in Section 2.5(c).

          "Compounded Interest" shall have the meaning set forth in Section 4.1.

          "Coupon Rate" shall have the meaning set forth in Section 2.5(a).

          "Declaration" means the Amended and Restated Declaration of Trust of
     Sterling Capital Trust II, a Delaware statutory business trust, dated as of
     March 21, 2001.

          "Deferred Interest" shall have the meaning set forth in Section 4.1.

                                       2
<PAGE>

          "Dissolution Event" means the dissolution of the Trust pursuant to the
     Declaration, and the distribution of the Debentures held by the Property
     Trustee pro rata to the holders of the Trust Securities in accordance with
     the Declaration.

          "Extended Interest Payment Period" shall have the meaning set forth in
     Section 4.1.

          "Federal Reserve" means the Board of Governors of the Federal Reserve
     System.

          "Global Debenture" shall have the meaning set forth in Section 2.4(a).

          "Holder" means any person in whose name at the time a Debenture is
     registered on the Securities Register.

          "Initial Optional Prepayment Date" means March 21, 2006.

          "Interest Payment Date" shall have the meaning set forth in Section
     2.5(a).

          "Investment Company Event" means the receipt by the Trust and the
     Company of an opinion of counsel, rendered by a law firm experienced in
     such matters, to the effect that, as a result of a change in law or
     regulation or a change in the interpretation or application of law or
     regulation by a legislature body, court, governmental agency or regulatory
     authority, the Trust is or will be considered an "investment company" that
     is required to be registered under the Investment Company Act of 1940, as
     amended, which change becomes effective on or after the date of original
     issuance of the Preferred Securities of the Trust.

          "Non Book-Entry Preferred Securities" shall have the meaning set forth
     in Section 2.4(a).

          "Prepayment Price" shall have the meaning set forth in Section 3.1.

          "Regulatory Capital Event" means that the Company shall have received
     an opinion of independent bank regulatory counsel experienced in such
     matters to the effect that, as a result of (a) any amendment to, or change
     (including any announced prospective change) in, the laws (or any
     regulations thereunder) of the United States or any rules, guidelines or
     policies of the Federal Reserve or any rules, guidelines or policies of any
     regulatory authority applicable to the Company, or (b) any official
     administrative pronouncement or judicial decision interpreting or applying
     such laws or regulations, which amendment or change is effective or such
     pronouncement or decision is announced on or after the date of original
     issuance of the Debentures, the Preferred Securities do not constitute, or
     within 90 days of the date thereof, will not constitute, Tier 1 Capital (or
     its equivalent) for purposes of the Federal Reserve's capital guidelines
     for bank holding companies; provided, however, that the distribution of the
     Debentures in connection with the liquidation of the Trust by the Company,
     as sponsor, and the treatment thereafter of the Debentures as other than
     Tier 1 Capital shall not in and of itself constitute a Regulatory Capital
     Event unless such liquidation shall have occurred in connection with a Tax
     Event.

                                       3
<PAGE>

          "Special Event" means an Investment Company Event, Tax Event or a
     Regulatory Capital Event, as the case may be.

          "Stated Maturity Date" means the date on which the Debentures mature
     and on which the principal shall be due and payable, together with all
     accrued and unpaid interest thereon including Compounded Interest and
     Additional Sums, if any, which date shall be March 21, 2031.

          "Tax Event" means that the Trust and the Company shall have received
     an opinion of counsel experienced in such matters to the effect that, as a
     result of (a) any amendment to, or change (including any announced
     prospective change) in, the laws or any regulations thereunder of the
     United States or any political subdivision or taxing authority thereof or
     therein, or (b) any official administrative pronouncement or judicial
     decision interpreting or applying such laws or regulations, which amendment
     or change is effective or which pronouncement or decision is announced on
     or after the date of the original issuance of the Debentures, there is more
     than an insubstantial risk that (i) the Trust is, or will be within 90 days
     of the date of such opinion, subject to United States federal income tax
     with respect to income received or accrued on the Debentures, (ii) interest
     payable by the Company on the Debentures is not, or within 90 days of the
     date thereof will not be, deductible by the Company, in whole or in part,
     for United States federal income tax purposes, or (iii) the Trust is, or
     will be within 90 days of the date of such opinion, subject to more than a
     de minimis amount of other taxes, duties or other governmental charges.

                                  ARTICLE II

                 GENERAL TERMS AND CONDITIONS OF THE DEBENTURES

     Section 2.1  Designation and Principal Amount.

     There is hereby authorized a series of Securities designated the "9.20%
Junior Subordinated Deferrable Interest Debentures due March 21, 2031," limited
in aggregate principal amount to $29,639,175 which amount shall be as set forth
in any written order of the Company for the authentication and delivery of
Debentures pursuant to Section 2.4 of the Indenture.

     Section 2.2  Maturity.

     The Debentures shall mature on March 21, 2031 (the "Stated Maturity Date").

     Section 2.3  Form and Payment.

     Except as provided in Section 2.4, the Debentures shall be issued in fully
registered certificated form without interest coupons. Principal and interest on
the Debentures issued in certificated form will be payable, the transfer of such
Debentures will be registrable and such Debentures will be exchangeable for
Debentures bearing identical terms and provisions at the office or agency of the
Company maintained for such purpose pursuant to Section 3.2 of the Indenture;
provided, however, that payment of interest with respect to Debentures (other
than a Global Debenture) may be made at the option of the Company (i) by check
mailed to the Holder

                                       4
<PAGE>

entitled thereto at such address as shall appear in the Securities Register or
(ii) by wire transfer to an account appropriately designated by the Holder
entitled thereto, provided that proper transfer instructions have been received
in writing by the relevant record date. Notwithstanding the foregoing, so long
as the Holder of any Debentures is the Property Trustee, the payment of the
principal of and interest (including Compounded Interest and Additional Sums, if
any) on such Debentures held by the Property Trustee will be made at such place
and to such account as may be designated by the Property Trustee.

     Section 2.4  Global Debenture.

        (a)  In connection with a Dissolution Event,

             (i) if any Preferred Securities are held in book-entry form, the
     related Debentures in certificated form shall be presented to the Trustee
     (if an arrangement with the Depositary has been maintained) by the Property
     Trustee in exchange for one or more global Debentures in an aggregate
     principal amount equal to the aggregate principal amount of all outstanding
     Debentures (a "Global Debenture"), to be registered in the name of the
     Depositary, or its nominee, and delivered by the Trustee to the Depositary
     for crediting to the accounts of its participants pursuant to the
     instructions of the Administrative Trustees. The Company upon any such
     presentation shall execute one or more Global Debentures in such aggregate
     principal amount and deliver the same to the Trustee for authentication and
     delivery in accordance with the Indenture and this First Supplemental
     Indenture. Payments on the Debentures issued as a Global Debenture will be
     made to the Depositary; and

             (ii) if any Preferred Securities are held in non book-entry
     certificated form, the related Debentures in certificated form may be
     presented to the Trustee by the Property Trustee and any certificate which
     represents Preferred Securities other than Preferred Securities in book-
     entry form held by the Depositary or its nominee ("Non Book-Entry Preferred
     Securities") will be deemed to represent beneficial interests in Debentures
     presented to the Trustee by the Property Trustee having an aggregate
     principal amount equal to the aggregate liquidation amount of the Non Book-
     Entry Preferred Securities until such Preferred Security certificates are
     presented to the Security Registrar for transfer or reissuance, at which
     time such Preferred Security certificates will be canceled and a Debenture,
     registered in the name of the holder of the Preferred Security certificate
     or the transferee of the holder of such Preferred Security certificate, as
     the case may be, with an aggregate principal amount equal to the aggregate
     liquidation amount of the Preferred Security certificate canceled, will be
     executed by the Company and delivered to the Trustee for authentication and
     delivery in accordance with the Indenture and this First Supplemental
     Indenture. Upon issue of such Debentures, Debentures with an equivalent
     aggregate principal amount that were presented by the Property Trustee to
     the Trustee will be deemed to have been canceled.

        (b) A Global Debenture shall represent the aggregate amount of
outstanding Debentures from time to time endorsed thereon; provided, that the
aggregate amount of

                                       5
<PAGE>

outstanding Debentures represented thereby may from time to time be reduced or
increased, as appropriate, to reflect exchanges or redemptions. Any endorsement
of a Global Debenture to reflect the amount of any increase or decrease in the
amount of outstanding Debentures represented thereby shall be made by the
Trustee, in accordance with instructions given by the Company as required by
this Section 2.4.

        (c) A Global Debenture may be transferred, in whole but not in part,
only to another nominee of the Depositary, or to a successor Depositary selected
or approved by the Company or to a nominee of such successor Depositary.

        (d) If (i) at any time the Depositary notifies the Company that it is
unwilling or unable to continue as Depositary or if at any time the Depositary
for such series shall no longer be registered or in good standing under the
Exchange Act, or other applicable statute or regulation, and a successor
Depositary for such series is not appointed by the Company within 90 days after
the Company receives such notice or becomes aware of such condition, as the case
may be, (ii) the Company at any time determines that the Debentures shall no
longer be solely represented by a Global Debenture or (iii) there shall have
occurred an Event of Default, then the Company shall execute, and, subject to
Article II of the Indenture, the Trustee, upon written notice from the Company,
shall authenticate and deliver the Debentures in definitive registered form
without coupons, in authorized denominations, and in an aggregate principal
amount equal to the principal amount of the Global Debenture, in exchange for
such Global Debenture. In such event the Company shall execute, and, subject to
Section 2.6 of the Indenture, the Trustee, upon receipt of an Officers'
Certificate evidencing such determination by the Company and a Company Order,
shall authenticate and make available for delivery the Debentures in definitive
registered form without coupons, in authorized denominations, and in an
aggregate principal amount equal to the principal amount of the Global
Debenture, in exchange for such Global Debenture. Upon the exchange of the
Global Debenture for such Debentures in definitive registered form without
coupons, in authorized denominations, the Global Debenture shall be canceled by
the Trustee. Such Debentures in definitive registered form issued in exchange
for the Global Debenture shall be registered in such names and in such
authorized denominations as the Depositary, pursuant to instructions from its
direct or indirect participants or otherwise, shall instruct the Trustee. The
Trustee shall deliver such Securities to the Depositary for delivery to the
Persons in whose names such Securities are so registered.

     Section 2.5  Interest.

        (a) Each Debenture will bear interest at the rate of 9.20% per annum
(the "Coupon Rate") from the most recent date to which interest has been paid or
duly provided for or, if no interest has been paid or duly provided for, from
the original date of issuance until the principal thereof becomes due and
payable, and on any overdue principal and, to the extent that payment of such
interest is enforceable under applicable law, on any overdue installment of
interest at the Coupon Rate, compounded quarterly, payable quarterly in arrears
on the first day of March, June, September and December of each year and on the
Stated Maturity Date (each, an "Interest Payment Date"), commencing on June 30,
2001, to the Person in whose name such Debenture or any predecessor Debenture is
registered at the close of business on the relevant record date, which will be
the 15th day of the month in which the relevant Interest Payment Date occurs,
except as otherwise provided pursuant to the provisions of Article IV hereof.

                                       6
<PAGE>

        (b) The amount of interest payable for any period will be computed on
the basis of a 360-day year of twelve 30-day months. Except as provided in the
following sentence, the amount of interest payable for any period shorter than a
full calendar month for which interest is computed, will be computed on the
basis of the actual number of days elapsed calendar month. In the event that any
Interest Payment Date falls on a day that is not a Business Day, then payment of
interest payable on such date will be made on the next succeeding day which is a
Business Day (and without any interest or other payment in respect of any such
delay), except that, if such Business Day is in the next succeeding calendar
year, such payment shall be made on the immediately preceding Business Day, in
each case with the same force and effect as if made on the date that such
interest otherwise would have been payable.

        (c) During such time as the Property Trustee is the holder of any
Debentures, the Company shall pay any additional amounts on the Debentures as
may be necessary in order that the amount of Distributions then due and payable
by the Trust on the outstanding Trust Securities shall not be reduced as a
result of any additional taxes, duties and other governmental charges to which
the Trust has become subject as a result of a Tax Event ("Additional Sums").
Whenever in the Indenture, this First Supplemental Indenture, or the Debentures
there is a reference in any context to the payment of principal of or interest
on the Debentures, such mention shall be deemed to include mention of the
payments of the Additional Sums provided for in this paragraph to the extent
that, in such context, Additional Sums are, were or would be payable in respect
thereof pursuant to the provisions of this paragraph and express mention of the
payment of Additional Sums (if applicable) in any provisions hereof shall not be
construed as excluding Additional Sums in those provisions hereof where such
express mention is not made; provided, however, that the deferral of the payment
of interest pursuant to Section 4.1 or the provisions of the Debentures shall
not defer the payment of any Additional Sums that may be due and payable.

                                  ARTICLE III

                          PREPAYMENT OF THE DEBENTURES

     Section 3.1  Special Event Prepayment.

     If, prior to the Initial Optional Prepayment Date, a Special Event has
occurred and is continuing, then notwithstanding Section 3.2(a) but subject to
Section 3.2(c), the Company shall have the right, at any time within 180 days
following the occurrence of such Special Event, upon (i) not less than 45 days
prior written notice to the Trustee, and (ii) not less than 30 days nor more
than 60 days prior written notice to the Holders, to prepay the Debentures, in
whole (but not in part), at a prepayment price equal to 100% of the principal
amount of the Debentures plus accrued and unpaid interest thereon (including
Compounded Interest), if any, and Additional Sums, if any, to the applicable
date of prepayment (the "Prepayment Price").  The Prepayment Price shall be paid
prior to 12:00 noon, New York City time, on the date of such prepayment or such
earlier time as the Company determines, provided that the Company shall deposit
with the Trustee an amount sufficient to pay the Prepayment Price by 10:00 a.m.,
New York City time, on the date such Prepayment Price is to be paid.

                                       7
<PAGE>

     Section 3.2  Optional Prepayment by Company.

        (a) Subject to the provisions of this Article III, the Company shall
have the right to prepay the Debentures, in whole or in part, from time to time,
on or after the Initial Optional Prepayment Date, at the Prepayment Price.

     If the Debentures are only partially prepaid pursuant to this Section 3.2,
the Debentures to be prepaid shall be selected on a pro rata basis not more than
60 days prior to the date fixed for prepayment from the outstanding Debentures
not previously called for prepayment, provided, however, that any such proration
may be made on the basis of the aggregate principal amount of Debentures held by
each Holder and may be made by making such adjustments as the Company deems fair
and appropriate in order that only Debentures in denominations of $25 or
integral multiples thereof shall be prepaid.  The Prepayment Price shall be paid
prior to 12:00 noon, New York time, on the date of such prepayment or at such
earlier time as the Company determines, provided further that the Company shall
deposit with the Trustee an amount sufficient to pay the Prepayment Price by
10:00 a.m., New York City time, on the date such Prepayment Price is to be paid.

        (b) Notwithstanding the first sentence of Section 3.2(a), upon the entry
of an order for dissolution of the Trust by a court of competent jurisdiction,
the Debentures thereafter will be subject to prepayment, in whole only, but not
in part, at the option of the Company, on or after the Initial Optional
Prepayment Date, at the Prepayment Price, and otherwise in accordance with this
Article III.

        (c) Any prepayment of Debentures pursuant to Section 3.1 or Section 3.2
shall be subject to the Company obtaining the prior approval of the Federal
Reserve, if such approval is then required under applicable capital guidelines
or policies of the Federal Reserve, and any other required regulatory approvals.

        (d) If a prepayment of some but not all of the Debentures would result
in the Preferred Securities ceasing to be quoted on the Nasdaq Stock Market or
any successor thereto or result in a delisting of the Preferred Securities from
any national securities exchange on which the Preferred Securities are then
listed, the Debentures will be subject to prepayment, in whole only, but not in
part, by the Company.

     Section 3.3  No Sinking Fund.

     The Debentures are not entitled to the benefit of any sinking fund.

                                  ARTICLE IV

                      EXTENSION OF INTEREST PAYMENT PERIOD

     Section 4.1 Extension of Interest Payment Period. So long as no Event of
Default has occurred and is continuing, the Company shall have the right, at any
time and from time to time during the term of the Debentures, to defer payments
of interest by extending the interest payment period of such Debentures for a
period not exceeding 20 consecutive quarterly periods, including the first such
quarterly period during such extension period (the "Extended Interest

                                       8
<PAGE>

Payment Period"), during which Extended Interest Payment Period no interest
shall be due and payable; provided that no Extended Interest Payment Period
shall end on a date other than an Interest Payment Date or extend beyond the
Stated Maturity Date. To the extent permitted by applicable law, interest, the
payment of which has been deferred because of the extension of the interest
payment period pursuant to this Section 4.1, will bear interest thereon at the
Coupon Rate compounded quarterly for each quarterly period of the Extended
Interest Payment Period ("Compounded Interest"). At the end of the Extended
Interest Payment Period, the Company shall pay all interest accrued and unpaid
on the Debentures, including any Additional Sums and Compounded Interest
(together, "Deferred Interest") that shall be payable to the Holders of the
Debentures in whose names the Debentures are registered in the Securities
Register on the record date for the first regular Interest Payment Date next
preceding the end of the Extended Interest Payment Period (which Interest
Payment Date shall be as specified in the Debenture). Before the termination of
any Extended Interest Payment Period, the Company may further defer payments of
interest by further extending such period, provided that such period, together
with all such previous and further extensions within such Extended Interest
Payment Period, shall not exceed 20 consecutive quarterly periods, including the
first such quarterly period during such Extended Interest Payment Period, end on
a date other than an Interest Payment Date or extend beyond the Stated Maturity
Date. Upon the termination of any Extended Interest Payment Period and the
payment of all Deferred Interest then due, the Company may commence a new
Extended Interest Payment Period, subject to the foregoing requirements. No
interest shall be due and payable during an Extended Interest Payment Period,
except at the end thereof, but the Company may prepay at any time all or any
portion of the interest accrued during an Extended Interest Payment Period.

     Section 4.2  Notice of Extension.

        (a) If the Property Trustee is the only registered holder of the
Debentures at the time the Company selects an Extended Interest Payment Period,
the Company shall give written notice to the Administrative Trustees, the
Property Trustee and the Trustee of its selection of such Extended Interest
Payment Period five Business Days before the earlier of (i) the next succeeding
date on which Distributions on the Trust Securities issued by the Trust are
payable, and (ii) the date the Trust is required to give notice of the record
date, or the date such Distributions are payable, to any national securities
exchange or to holders of the Preferred Securities issued by the Trust, but in
any event at least five Business Days before such record date.

        (b) If the Property Trustee is not the only holder of the Debentures at
the time the Company selects an Extended Interest Payment Period, the Company
shall give the Holders of the Debentures and the Trustee written notice of its
selection of such Extended Interest Payment Period at least 10 Business Days
before the earlier of (i) the next succeeding Interest Payment Date, or (ii) the
date the Company is required to give notice of the record or payment date of
such interest payment to any national securities exchange.

        (c) The quarterly period in which any notice is given pursuant to
paragraphs (a) or (b) of this Section 4.2 shall be counted as one of the 20
quarterly periods permitted in the maximum Extended Interest Payment Period
permitted under Section 4.1.

                                       9
<PAGE>

     Section 4.3  Limitation of Transactions.

     If (i) the Company shall exercise its right to defer payment of interest as
provided in Section 4.1 and the Extended Interest Payment Period is continuing,
(ii) there shall have occurred any event, of which the Company has actual
knowledge that (a) is, or with the giving of notice or the lapse of time, or
both, would constitute, an Event of Default and (b) in respect of which the
Company shall not have taken reasonable steps to cure, or (iii) the Debentures
are held by the Property Trustee and the Company shall be in default with
respect to its payment obligations under the Preferred Securities Guarantee,
then the Company will not: (i) declare or pay any dividends or distributions on,
or redeem, purchase, acquire, or make a liquidation payment with respect to, any
of the Company's capital stock (which includes common and preferred stock)
(other than (1) dividends or distributions in shares of, or options, warrants or
rights to subscribe for or purchase shares of, Common Stock of the Company, (2)
any declaration of a dividend in connection with the implementation of a
stockholder's rights plan, or the issuance of stock under any such plan in the
future, or the redemption or repurchase of any such rights pursuant thereto, (3)
as a result of a reclassification of any class or series of the Company's
capital stock solely into another class or series of the Company's capital
stock, (4) the purchase of fractional shares resulting from such
reclassification or pursuant to the conversion or exchange provisions of such
capital stock or any security convertible or exchangeable into shares of the
Company's capital stock, and (5) purchases of Common Stock related to the
issuance of Common Stock or rights under any of the Company's benefit plans for
its directors, officers or employees or any of the Company's dividend
reinvestment plans); (ii) make any payment of principal, premium, if any, or
interest on or repay or repurchase or redeem any debt securities of the Company
(including Other Debentures) that rank pari passu with or junior in right of
payment to the Debentures; or (iii) make any guarantee payments (other than
payments under the Preferred Securities Guarantee) with respect to any guarantee
by the Company of the debt securities of any Subsidiary of the Company
(including Other Guarantees) if such guarantee ranks pari passu or junior in
right of payment to the Debentures.

                                   ARTICLE V

                         CHANGE OF STATED MATURITY DATE

     Section 5.1  Change of Stated Maturity Date.

     So long as no Event of Default has occurred and is continuing and subject
to Section 5.2(c), the Company shall have the right, at any time, but only once,
during the term of the Debentures, to reduce the term of the Debentures by
selecting a date, not earlier than the Initial Optional Prepayment Date, as the
new "Stated Maturity Date" for the purposes of this First Supplemental Indenture
and the Debentures; provided that such new "Stated Maturity Date" is an Interest
Payment Date and provided further that such new "Stated Maturity Date" shall not
be later than March 21, 2031 or be earlier than any date that has occurred.

     Section 5.2  Notice of Change of Stated Maturity Date.

        (a) If the Property Trustee is the only registered holder of the
Debentures at the time the Company designates a new "Stated Maturity Date"
pursuant to Section 5.1, the

                                       10
<PAGE>

Company shall give written notice to the Administrative Trustees, the Property
Trustee and the Trustee of its selection of such new "Stated Maturity Date" five
Business Days before the earlier of (i) the next succeeding date on which
Distributions on the Trust Securities issued by the Trust are payable, and (ii)
the date the Trust is required to give notice of the record date, or the date
such Distributions are payable, to any national securities exchange or to
holders of the Preferred Securities issued by the Trust, but in any event at
least five Business Days before such record date.

        (b) If the Property Trustee is not the only holder of the Debentures at
the time the Company selects a new "Stated Maturity Date" pursuant to Section
5.1, the Company shall give the Holders of the Debentures and the Trustee
written notice of its selection of such new "Stated Maturity Date" at least 10
Business Days before the earlier of (i) the next succeeding Interest Payment
Date, or (ii) the date the Company is required to give notice of the record or
payment date of such interest payment to any national securities exchange.

        (c) It is a condition precedent to the exercise of the Company's right
under Section 5.1 that the Company shall have obtained the approval of the
Federal Reserve for such exercise, if such approval is then required for such
exercise under applicable laws, regulations, capital guidelines or policies of
the Federal Reserve, and any other regulatory approval required for such
exercise.

        (d) Any selection of a new "Stated Maturity Date" shall have no effect
under this First Supplemental Indenture unless and until the Company and the
Trustee have given the written notices required by Section 5.2(a) or (b). If all
such notices have been given in accordance with Section 5.2 (a) or (b), then the
new "Stated Maturity Date" selected in accordance with Section 5.1 shall become
the Stated Maturity Date for the Debentures with effect from the date specified
in such notices.

                                  ARTICLE VI

                                   EXPENSES

     Section 6.1  Payment of Expenses.

     In connection with the offering, sale and issuance of the Debentures to the
Property Trustee and in connection with the sale of the Trust Securities by the
Trust, the Company, in its capacity as borrower with respect to the Debentures,
shall:

        (a) pay all costs and expenses relating to the offering, sale and
issuance of the Debentures, including commissions to the underwriter payable
pursuant to the Underwriting Agreement and compensation of the Trustee under the
Indenture in accordance with the provisions of Section 6.6 of the Indenture;

        (b) pay all costs and expenses of the Trust (including, but not limited
to, costs and expenses relating to the organization of the Trust), the offering,
sale and issuance of the Trust Securities (including commissions to the
underwriters in connection therewith), the fees and expenses of the Property
Trustee and the Delaware Trustee, the costs and expenses relating

                                       11
<PAGE>

to the operation of the Trust, including without limitation, costs and expenses
of accountants, attorneys, statistical or bookkeeping services, expenses for
printing and engraving and computing or accounting equipment, paying agent(s),
registrar(s), transfer agent(s), duplicating, travel and telephone and other
telecommunications expenses and costs and expenses incurred in connection with
the acquisition, financing, and disposition of assets of the Trust;

        (c) be primarily and fully liable for any indemnification obligations
arising with respect to the Declaration;

        (d) pay any and all taxes (other than United Sates withholding taxes
attributable to the Trust or its assets) and all liabilities, costs and expenses
with respect to such taxes of the Trust; and

        (e) pay all other fees, expenses, debts and obligations (other than in
respect of the Trust Securities).

     The provisions of this Section shall survive the termination of this First
Supplemental Indenture.

     Section 6.2  Payment Upon Resignation or Removal.

     Upon termination of this First Supplemental Indenture or the Indenture or
the removal or resignation of the Trustee, unless otherwise stated, the Company
shall pay to the Trustee all amounts accrued to the date of such termination,
removal or resignation that are payable pursuant to Section 6.6 of the
Indenture.  Upon termination of the Declaration or the removal or resignation of
the Delaware Trustee or the Property Trustee, as the case may be, pursuant to
Section 5.7 of the Declaration, the Company shall pay to the Delaware Trustee or
the Property Trustee, as the case may be, all amounts accrued to the date of
such termination, removal or resignation.

                                  ARTICLE VII

                          COVENANT TO LIST ON EXCHANGE

     Section 7.1  Listing on an Exchange.

     If the Debentures are distributed to the holders of the Securities issued
by the Trust, and the Preferred Securities are then so listed, the Company will
use commercially reasonable efforts to list such Debentures on the Nasdaq Stock
Market or on such other exchange as the Preferred Securities are then listed.

                                       12
<PAGE>

                                 ARTICLE VIII

                               FORM OF DEBENTURE

     Section 8.1  Form of Debenture.

     The Debentures and the Trustee's Certificate of Authentication to be
endorsed thereon shall be substantially in the form of Exhibit A, the terms of
which are incorporated in and made a part of this First Supplemental Indenture.

                                  ARTICLE IX

                          ORIGINAL ISSUE OF DEBENTURES

     Section 9.1  Original Issue of Debentures.

     Debentures in the aggregate principal amount of $29,639,175, may, upon
execution of this First Supplemental Indenture or upon any written order of the
Company setting forth the amount therefor, be executed by the Company and
delivered to the Trustee for authentication, and the Trustee shall thereupon
authenticate and deliver said Debentures to or upon the written order of the
Company, signed by its Chairman, its President, or any Vice President and its
Treasurer, its Secretary, any Assistant Treasurer, or any Assistant Secretary,
without any further action by the Company.

                                   ARTICLE X

                                 MISCELLANEOUS

     Section 10.1  Ratification of Indenture.

     The Indenture, as supplemented by this First Supplemental Indenture, is in
all respects ratified and confirmed, and this First Supplemental Indenture shall
be deemed part of the Indenture in the manner and to the extent herein and
therein provided.

     Section 10.2  Trustee Not Responsible for Recitals.

     The recitals herein contained are made by the Company and not by the
Trustee, and the Trustee assumes no responsibility for the correctness thereof.
The Trustee makes no representation as to the validity or sufficiency of this
First Supplemental Indenture.

     Section 10.3  Governing Law.

     This First Supplemental Indenture and each Debenture shall be deemed to be
a contract made under the internal laws of the State of New York, and for all
purposes shall be construed in accordance with the laws of said State.

                                       13
<PAGE>

     Section 10.4  Counterparts.

     This First Supplemental Indenture may be executed in any number of
counterparts each of which shall be an original; but such counterparts shall
together constitute but one and the same instrument.

     IN WITNESS WHEREOF, the parties hereto have caused this First Supplemental
Indenture to be duly executed by their respective officers thereunto duly
authorized as of the day and year first above written.

[Seal]                              STERLING BANCSHARES, INC.

Attest:

    /s/ JAMES W. GOOLSBY, JR.
By:                                 By: /s/ GEORGE MARTINEZ
   --------------------------          --------------------------
Name: James W. Goolsby, Jr.         Name:  George Martinez
     ----------------------
Title: Assistant Secretary          Title:  Chairman
      ---------------------

                                    BANKERS TRUST COMPANY, as Trustee

                                    By: /s/ SUSAN JOHNSON
                                       ----------------------------
                                    Name:  Susan Johnson
                                    Title:  Vice President

                                       14
<PAGE>

STATE OF TEXAS      (S)
                    (S)
COUNTY OF HARRIS    (S)

          On the 20th day of March, 2001 before me personally came George
Martinez, to me known, who, being by me duly sworn, did depose and say that he
resides in Houston, Texas; that he is Chairman of Sterling Bancshares, Inc., one
of the corporations described in and which executed the above instrument; that
he knows the corporate seal of said corporation; that the seal affixed to the
said instrument is such corporate seal; that it was so affixed by authority of
the Board of Directors of said corporation; and that he signed his name thereto
by like authority.

                                          /s/  CANDACE BAUER
                                          --------------------------------
                                          Notary Public, State Of Texas
[seal]                                    Commission expires: September 19, 2003

                                       15
<PAGE>

                                   EXHIBIT A

                          (FORM OF FACE OF DEBENTURE)

No. __________                                   Principal Amount: $____________
                                                 CUSIP No. _____________________

     [IF THE DEBENTURE IS A GLOBAL DEBENTURE, INSERT:  THIS DEBENTURE IS A
GLOBAL DEBENTURE WITHIN THE MEANING OF THE INDENTURE HEREINAFTER REFERRED TO AND
IS REGISTERED IN THE NAME OF A DEPOSITARY OR A NOMINEE OF A DEPOSITARY. THIS
DEBENTURE IS EXCHANGEABLE FOR DEBENTURES REGISTERED IN THE NAME OF A PERSON
OTHER THAN THE DEPOSITARY OR ITS NOMINEE ONLY IN THE LIMITED CIRCUMSTANCES
DESCRIBED IN THE INDENTURE, AND NO TRANSFER OF THIS DEBENTURE (OTHER THAN A
TRANSFER OF THIS DEBENTURE AS A WHOLE BY THE DEPOSITARY TO A NOMINEE OF THE
DEPOSITARY OR BY A NOMINEE OF THE DEPOSITARY TO THE DEPOSITARY OR ANOTHER
NOMINEE OF THE DEPOSITARY) MAY BE REGISTERED EXCEPT IN LIMITED CIRCUMSTANCES.

     IF THE DEPOSITARY FOR THIS DEBENTURE IS THE DEPOSITORY TRUST COMPANY, A NEW
YORK CORPORATION ("DTC"), THEN, UNLESS THIS DEBENTURE IS PRESENTED BY AN
AUTHORIZED REPRESENTATIVE OF THE DTC TO THE ISSUER OR ITS AGENT FOR REGISTRATION
OF TRANSFER, EXCHANGE OR PAYMENT, AND ANY DEBENTURE ISSUED IS REGISTERED IN THE
NAME OF CEDE & CO. OR IN SUCH OTHER NAME AS REQUESTED BY AN AUTHORIZED
REPRESENTATIVE OF DTC (AND ANY PAYMENT HEREON IS MADE TO CEDE & CO. OR TO SUCH
OTHER ENTITY AS IS REQUESTED BY AN AUTHORIZED REPRESENTATIVE OF DTC), ANY
TRANSFER, PLEDGE OR OTHER USE HEREOF FOR VALUE OR OTHERWISE BY OR TO ANY PERSON
IS WRONGFUL IN AS MUCH AS SINCE THE REGISTERED OWNER HEREOF, CEDE & CO., HAS AN
INTEREST HEREIN.]

                                      A-1
<PAGE>

                           STERLING BANCSHARES, INC.

         9.20% SERIES JUNIOR SUBORDINATED DEFERRABLE INTEREST DEBENTURE
                               DUE MARCH 21, 2031

     Sterling Bancshares, Inc., a Texas corporation (the "Company", which term
includes any successor Person under the Indenture hereinafter referred to), for
value received, hereby promises to pay to _______ or registered assigns, [the
principal sum of] [$___________ Dollars]/1/  [specified on Schedule A attached
hereto]/2/ on March 21, 2031 (subject to no earlier date having been designated
in accordance with Article V of the First Supplemental Indenture to the
Indenture, the "Stated Maturity Date"), unless previously prepaid or redeemed,
and to pay interest on the outstanding principal amount hereof from March 21,
2001, or from the most recent Interest Payment Date (as defined below) to which
interest has been paid or duly provided for, quarterly (subject to deferral as
set forth herein) in arrears on March 31, June 30, September 30 and December 31
of each year, commencing June 30, 2001, and on the Stated Maturity Date (each
such date, an "Interest Payment Date") at the rate of 9.20% per annum until the
principal hereof shall have become due and payable, and on any overdue principal
and (without duplication and to the extent that payment of such interest is
enforceable under applicable law) on any overdue installment of interest at the
same rate per annum compounded quarterly. The amount of interest payable on any
Interest Payment Date shall be computed on the basis of a 360-day year of twelve
30-day months and, for any period less than a full calendar month, the number of
days elapsed in such month. In the event that any date on which the principal
of, or interest on this Debenture is payable is not a Business Day, then the
payment payable on such date will be made on the next succeeding day that is a
Business Day (and without any interest or other payment in respect of any such
delay), except that if such next succeeding Business Day falls in the next
calendar year, then such payment shall be made on the immediately preceding
Business Day, in each case with the same force and effect as if made on such
date. Pursuant to the First Supplemental Indenture to the Indenture, in certain
circumstances the Company will be required to pay Additional Sums and Compounded
Interest (each as defined in the First Supplemental Indenture to the Indenture)
with respect to this Debenture.

     The interest installment so payable, and punctually paid or duly provided
for, on any Interest Payment Date will, as provided in the Indenture, be paid to
the Person in whose name this Debenture (or one or more Predecessor Securities,
as defined in said Indenture) is registered at the close of business on the
regular record date for such interest installment, which shall be at the close
of business on the 15th day of the month in which the relevant Interest Payment
Date falls.  Payments of interest may be deferred by the Company pursuant to the
provisions of Article IV of the First Supplemental Indenture to the Indenture.
Any such interest installment not punctually paid or duly provided for shall
forthwith cease to be payable to the Holders on such regular record date and may
be paid to the Person in whose name this Debenture (or one or more Predecessor
Securities) is registered at the close of business on a special record date to
be fixed by the Trustee for the payment of such defaulted interest, notice
whereof shall be given to the Holders of this series of Debentures not less than
10 days prior to such special record date, or may be paid at any time in any
other lawful manner not inconsistent with the requirements of any

----------------------
/1/   Insert in Definitive Securities only.
/2/   Insert in Global Securities only.

                                      A-2
<PAGE>

securities exchange on which the Debentures may be listed, and upon such notice
as may be required by such exchange, all as more fully provided in the
Indenture.

     The principal of and interest (including Compounded Interest and Additional
Sums, if any) on this Debenture shall be payable at the office or agency of the
Trustee maintained for that purpose in any coin or currency of the United States
of America that at the time of payment is legal tender for payment of public and
private debts; provided, however, that, payment of interest may be made at the
option of the Company by (i) check mailed to the Holder at such address as shall
appear in the Securities Register or (ii) by transfer to an account maintained
by the Person entitled thereto, provided that proper written transfer
instructions have been received by the relevant record date.  Notwithstanding
the foregoing, so long as the Holder of this Debenture is the Property Trustee,
the payment of the principal of and interest (including Compounded Interest and
Additional Sums, if any,) on this Debenture will be made at such place and to
such account as may be designated by the Property Trustee.

     So long as no Event of Default has occurred and is continuing, and subject
to the Company having received prior approval of the Federal Reserve if then
required under applicable capital guidelines, policies or regulations of the
Federal Reserve, the Company shall have the right, at any time, but only once,
during the term of the Debentures, to reduce the term of the Debentures by
selecting a date, not earlier than the Initial Optional Prepayment Date, as the
new "Stated Maturity Date"; provided that such new "Stated Maturity Date" is an
Interest Payment Date and provided further that such new "Stated Maturity Date"
shall not be later than March 21, 2031 or be earlier than any date that has
occurred.

     The indebtedness evidenced by this Debenture is, to the extent provided in
the Indenture, subordinate and junior in right of payment to the prior payment
in full of all Senior Indebtedness, and this Debenture is issued subject to the
provisions of the Indenture with respect thereto.  Each Holder of this
Debenture, by accepting the same, (a) agrees to and shall be bound by such
provisions, (b) authorizes and directs the Trustee on his or her behalf to take
such action as may be necessary or appropriate to acknowledge or effectuate the
subordination so provided and (c) appoints the Trustee his or her attorney-in-
fact for any and all such purposes.  Each Holder hereof, by his or her
acceptance hereof, hereby waives all notice of the acceptance of the
subordination provisions contained herein and in the Indenture by each Holder of
Senior Indebtedness, whether now outstanding or hereafter incurred, and waives
reliance by each such Holder upon said provisions.

     This Debenture shall not be entitled to any benefit under the Indenture
hereinafter referred to, be valid or become obligatory for any purpose until the
Certificate of Authentication hereon shall have been signed by or on behalf of
the Trustee.

     The provisions of this Debenture are continued on the reverse side hereof
and such provisions shall for all purposes have the same effect although fully
set forth at this place.

                                      A-3
<PAGE>

     IN WITNESS WHEREOF, the Company has caused this instrument to be duly
executed and sealed.

     Dated: March __, 2001.

Attest:                                  STERLING BANCSHARES, INC.

By:_______________________               By:_______________________

Name:_____________________               Name:_____________________

Title:____________________               Title:____________________

                    (FORM OF CERTIFICATE OF AUTHENTICATION)

                         CERTIFICATE OF AUTHENTICATION

     This is one of the Securities referred to in the within-mentioned Indenture
and First Supplemental Indenture.

BANKERS TRUST COMPANY,
as Trustee

By ______________________
   Authorized Officer

                                      A-4
<PAGE>

                         (FORM OF REVERSE OF SECURITY)

     This Debenture is one of the series of Securities of the Company,
designated as the 9.20% Junior Subordinated Deferrable Interest Debentures due
March 21, 2031 (herein sometimes referred to as the "Debentures"), specified in
the Indenture, all issued or to be issued in one or more series under and
pursuant to an Indenture, dated as of March 21, 2001, duly executed and
delivered between the Company and Bankers Trust Company, as Trustee (the
"Trustee"), as supplemented by the First Supplemental Indenture dated as of
March 21, 2001 between the Company and the Trustee (the Indenture, as so
supplemented, being referred to as the "Indenture") to which Indenture reference
is hereby made for a description of the rights, limitations of rights,
obligations, duties and immunities thereunder of the Trustee, the Company and
the Holders of the Debentures.  By the terms of the Indenture, the Securities
are issuable in series that may vary as to amount, date of maturity, rate of
interest and in other respects as provided in the Indenture.  This series of
Debentures is limited in aggregate principal amount as specified in the First
Supplemental Indenture.

     Upon the occurrence and continuation of a Special Event, as defined in the
First Supplemental Indenture, prior to March 21, 2006 (the "Initial Optional
Prepayment Date"), the Company shall have the right, at any time within 180 days
following the occurrence of such Special Event, to prepay this Debenture in
whole (but not in part) at the Prepayment Price.  "Prepayment Price" shall mean
an amount in cash equal to 100% of the principal amount thereof plus accrued and
unpaid interest on the Debenture to be so prepaid (including Compounded Interest
and Additional Sums, if any) to the date of such prepayment.

     In addition, subject to the Company having received the prior approval of
the Federal Reserve System (the "Federal Reserve"), if then required under
applicable guidelines or policies of the Federal Reserve, and any other required
regulatory approvals, the Company shall have the right to prepay this Debenture,
in whole or in part, at any time on or after the Initial Optional Prepayment
Date at the Prepayment Price.

     The Prepayment Price shall be paid prior to 12:00 noon, New York City time,
on the date of such prepayment or at such earlier time as the Company
determines, provided, that the Company shall deposit with the Trustee an amount
sufficient to pay the applicable Prepayment Price by 10:00 a.m., New York City
time, on the date such Prepayment Price is to be paid.  Any prepayment pursuant
to this paragraph will be made upon not less than 30 days or more than 60 days
notice.  If the Debentures are only partially prepaid by the Company pursuant to
an Optional Prepayment, the particular Debentures to be prepaid shall be
selected on a pro rata basis not more than 60 days prior to the date fixed for
prepayment from the outstanding Debentures not previously called for prepayment,
provided, however, that any such proration may be made on the basis of the
aggregate principal amount of Debentures held by each Holder thereof and may be
made by making such adjustments as the Company deems fair and appropriate in
order that only Debentures in denominations of $25 or integral multiples thereof
shall be prepaid.

     In the event of prepayment of this Debenture in part only, a new Debenture
or Debentures for the portion hereof that has not been prepaid will be issued in
the name of the Holder hereof upon the cancellation hereof.

     Notwithstanding the foregoing, any prepayment of Debentures by the Company
shall be subject to the prior approval of the Federal Reserve, if such approval
is then required under

                                      A-5
<PAGE>

applicable capital guidelines or policies of the Federal Reserve, and the
receipt of any other required regulatory approvals.

     In case an Event of Default, as defined in the Indenture, shall have
occurred and be continuing, the principal of all of the Debentures may be
declared, and upon such declaration shall become, due and payable, in the
manner, with the effect and subject to the conditions provided in the Indenture.

     The Indenture contains provisions permitting the Company and the Trustee,
with the consent of the Holders of a majority in aggregate principal amount of
the Securities of each series affected at the time outstanding, as defined in
the Indenture, to execute supplemental indentures for the purpose of adding any
provisions to or changing in any manner or eliminating any of the provisions of
the Indenture or of any supplemental indenture or of modifying in any manner the
rights of the Holders of the Securities; provided, however, that no such
supplemental indenture shall, without the consent of each Holder of Securities
then outstanding and affected thereby, (i) extend or change the Stated Maturity
Date of any Securities (except as expressly permitted in accordance with the
terms of any supplemental indenture establishing such series of Securities in
accordance with Section 2.2 of the Indenture), or reduce the principal amount
thereof, or reduce any amount payable on redemption thereof, or reduce the rate
of interest thereon, or extend the time of payment of interest thereon (except
as expressly permitted in accordance with the terms of any supplemental
indenture establishing such series of Securities in accordance with Section 2.2
of the Indenture), or make the principal of, or interest on, the Securities
payable in any coin or currency other than U.S. dollars, or impair or affect the
right of any holder of Securities to institute suit for the payment thereof, or
(ii) reduce the aforesaid percentage amount of Securities, the Holders of which
are required to consent to any such supplemental indenture.  The Indenture also
contains provisions permitting the Holders of a majority in aggregate principal
amount of the Securities of any series at the time outstanding affected thereby,
on behalf of all of the Holders of the Securities of such series, to waive any
past default in the performance of any of the covenants contained in the
Indenture, or established pursuant to the Indenture with respect to such series,
and its consequences, except a default in the payment of the principal of or
interest on any of the Securities or a default in respect of any covenant or
provision under which the Indenture cannot be modified or amended without the
consent of each Holder of Securities affected thereby.  Any such consent or
waiver by the holder of this Debenture (unless revoked as provided in the
Indenture) shall be conclusive and binding upon such Holder and upon all future
holders and owners of this Debenture and of any Debenture issued in exchange
herefor or in place hereof, irrespective of whether or not any notation of such
consent or waiver is made upon this Debenture.

     No reference herein to the Indenture and no provision of this Debenture or
of the Indenture shall alter or impair the obligation of the Company, which is
absolute and unconditional, to pay the principal of and interest (including
Compounded Interest and Additional Sums, if any) on this Debenture at the time
and place and at the rate and in the money herein prescribed.

     So long as no Event of Default shall have occurred and be continuing, the
Company shall have the right, at any time and from time to time during the term
of the Debentures, to defer payments of interest by extending the interest
payment period of such Debentures for a period not exceeding 20 consecutive
quarterly periods, including the first such quarterly period during such
extension period, and not extending beyond the Stated Maturity Date of the
Securities (an

                                      A-6
<PAGE>

"Extended Interest Payment Period") or ending on a date other than an Interest
Payment Date, at the end of which period the Company shall pay all interest then
accrued and unpaid (together with interest thereon at the rate specified for the
Debentures to the extent that payment of such interest is enforceable under
applicable law). Before the termination of any such Extended Interest Payment
Period, the Company may further defer payments of interest by further extending
such Extended Interest Payment Period, provided that such Extended Interest
Payment Period, together with all such previous and further extensions within
such Extended Interest Payment Period, (i) shall not exceed 20 consecutive
quarterly periods, including the first quarterly period during such Extended
Interest Payment Period, (ii) shall not end on any date other than an Interest
Payment Date, and (iii) shall not extend beyond the Stated Maturity Date of the
Debentures. Upon the termination of any such Extended Interest Payment Period
and the payment of all accrued and unpaid interest and any additional amounts
then due, the Company may commence a new Extended Interest Payment Period,
subject to the foregoing requirements.

     The Company has agreed that it will not: (i) declare or pay any dividends
or distributions on, or redeem, purchase, acquire, or make a liquidation payment
with respect to, any of the Company's capital stock (which includes common and
preferred stock) (other than (a) dividends or distributions in shares of, or
options, warrants or rights to subscribe for or purchase shares of, Common Stock
of the Company, (b) any declaration of a dividend in connection with the
implementation of a stockholder's rights plan, or the issuance of stock under
any such plan in the future, or the redemption or repurchase of any such rights
pursuant thereto, (c) as a result of a reclassification of any class or series
of the Company's capital stock solely into another class or series of the
Company's capital stock, (d) the purchase of fractional shares resulting from
such a reclassification or pursuant to the conversion or exchange provisions of
such capital stock or any security convertible or exchangeable into shares of
the Company's capital stock, and (e) purchases of Common Stock related to the
issuance of Common Stock or rights under any of the Company's benefit plans for
its directors, officers or employees or any of the Company's dividend
reinvestment plans); (ii) make any payment of principal, interest on or repay or
prepay or repurchase or redeem any debt securities of the Company that rank pari
passu with or junior in right of payment to the Debentures; or (iii) make any
guarantee payments with respect to any guarantee (other than payments under the
Preferred Securities Guarantee) by the Company of the debt securities of any
Subsidiary of the Company if such guarantee ranks pari passu or junior in right
of payment to the Debentures, if at such time (1) there shall have occurred any
event of which the Company has actual knowledge that (a) is or, with the giving
of notice or the lapse of time, or both, would be, an Event of Default and (b)
in respect of which the Company shall not have taken reasonable steps to cure,
(2) the Company shall be in default with respect to its payment obligations
under the Preferred Securities Guarantee or (3) the Company shall have given
notice of its election of the exercise of its right to extend the interest
payment period and any such extension shall be continuing.

     Subject to (i) the prior approval of the Federal Reserve, if such approval
is then required under applicable capital guidelines or policies of the Federal
Reserve and the receipt of any other required regulatory approval, and (ii) the
receipt by the Company of an opinion of counsel to the effect that such
distribution will not be a taxable event to holders of Preferred Securities, the
Company will have the right at any time to liquidate the Trust and cause the
Debentures to be distributed to the holders of the Trust Securities in
liquidation of the Trust.

                                      A-7
<PAGE>

     The Debentures of this series are issuable only in registered form without
coupons in denominations of $25 and any integral multiple thereof.  As provided
in the Indenture and subject to the transfer restrictions limitations as may be
contained herein and therein from time to time, this Debenture is transferable
by the holder hereof on the Securities Register of the Company, upon surrender
of this Debenture for registration of transfer at the office or agency of the
Company in the City and State of New York accompanied by a written instrument or
instruments of transfer in form satisfactory to the Company or the Trustee duly
executed by the holder hereof or his attorney duly authorized in writing, and
thereupon one or more new Debentures of authorized denominations and for the
same aggregate principal amount and series will be issued to the designated
transferee or transferees. No service charge will be made for any such
registration of transfer, but the Company may require payment of a sum
sufficient to cover any tax or other governmental charge payable in relation
thereto.

     Prior to due presentment for registration of transfer of this Debenture,
the Company, the Trustee, any authenticating agent, any paying agent, any
transfer agent and the registrar may deem and treat the registered holder hereof
as the absolute owner hereof (whether or not this Debenture shall be overdue and
notwithstanding any notice of ownership or writing hereon made by anyone other
than the Security Registrar) for the purpose of receiving payment of or on
account of the principal hereof and (subject to the Indenture) interest due
hereon and for all other purposes, and neither the Company nor the Trustee nor
any authenticating agent nor any paying agent nor any transfer agent nor any
registrar shall be affected by any notice to the contrary.

     No recourse shall be had for the payment of the principal of, or interest
on this Debenture, or for any claim based hereon, or otherwise in respect
hereof, or based on or in respect of the Indenture, against any incorporator,
stockholder, officer or director, past, present or future, as such, of the
Company or of any predecessor or successor Person, whether by virtue of any
constitution, statute or rule of law, or by the enforcement of any assessment or
penalty or otherwise, all such liability being, by the acceptance hereof and as
part of the consideration for the issuance hereof, expressly waived and
released.

     All terms used in this Debenture that are defined in the Indenture shall
have the meanings assigned to them in the Indenture.

     THE INDENTURE AND THE DEBENTURES SHALL BE GOVERNED BY AND CONSTRUED IN
ACCORDANCE WITH THE LAWS OF THE STATE OF NEW YORK.

                                      A-8
<PAGE>

                                   SCHEDULE A

     The initial aggregate principal amount of Debentures evidenced by the
Certificate to which this Schedule is attached is ____________________ (having
an aggregate liquidation amount of __________________).  The notations in the
following table evidence decreases and increases in the aggregate principal
amount of the Debentures evidenced by such Certificate.

<TABLE>
<CAPTION>
 <S>                          <C>                      <C>                       <C>
Decrease in aggregate     Increase in aggregate      Aggregate principal
 principal amount of       principal amount of      amount of Debentures
 Debentures                    Debentures           remaining after such
                                                    decrease or increase      Notation by Registrar
----------------------------------------------------------------------------------------------------

----------------------------------------------------------------------------------------------------
</TABLE>

 * Append to Global Debentures only.

                                  Schedule A<PAGE>

                                                                     EXHIBIT 4.6

Number of                                                  Aggregate Liquidation
Preferred Securities                                       Amount:  $28,750,000
1,150,000                                                  CUSIP NO. 85915H 20 6

       Certificate Evidencing 9.20% Cumulative Trust Preferred Securities

                                       of

                      Sterling Bancshares Capital Trust II

                  9.20% Cumulative Trust Preferred Securities
                (liquidation amount $25 per Preferred Security)

     THIS PREFERRED SECURITY IS A GLOBAL PREFERRED SECURITY WITHIN THE MEANING
OF THE DECLARATION HEREINAFTER REFERRED TO AND IS REGISTERED IN THE NAME OF THE
DEPOSITORY TRUST COMPANY (THE "CLEARING AGENCY") OR A NOMINEE OF THE CLEARING
AGENCY.  THIS PREFERRED SECURITY IS EXCHANGEABLE FOR PREFERRED SECURITIES
REGISTERED IN THE NAME OF A PERSON OTHER THAN THE CLEARING AGENCY OR ITS NOMINEE
ONLY IN THE LIMITED CIRCUMSTANCES DESCRIBED IN THE DECLARATION AND NO TRANSFER
OF THIS PREFERRED SECURITY (OTHER THAN A TRANSFER OF THIS PREFERRED SECURITY AS
A WHOLE BY THE CLEARING AGENCY TO A NOMINEE OF THE CLEARING AGENCY OR BY A
NOMINEE OF THE CLEARING AGENCY TO THE CLEARING AGENCY OR ANOTHER NOMINEE OF THE
CLEARING AGENCY) MAY BE REGISTERED EXCEPT IN LIMITED CIRCUMSTANCES.

     UNLESS THIS SECURITY IS PRESENTED BY AN AUTHORIZED REPRESENTATIVE OF THE
CLEARING AGENCY TO THE ISSUER OR ITS AGENT FOR REGISTRATION OF TRANSFER,
EXCHANGE OR PAYMENT, AND ANY SECURITY ISSUED IS REGISTERED IN THE NAME OF CEDE &
CO. OR IN SUCH OTHER NAME AS REQUESTED BY AN AUTHORIZED REPRESENTATIVE OF THE
CLEARING AGENCY (AND ANY PAYMENT HEREON IS MADE TO CEDE & CO. OR TO SUCH OTHER
ENTITY AS IS REQUESTED BY AN AUTHORIZED REPRESENTATIVE OF THE CLEARING AGENCY),
ANY TRANSFER, PLEDGE OR OTHER USE HEREOF FOR VALUE OR OTHERWISE BY OR TO ANY
PERSON IS WRONGFUL IN AS MUCH AS SINCE THE REGISTERED OWNER HEREOF, CEDE & CO.,
HAS AN INTEREST HEREIN.

     Sterling Bancshares Capital Trust II, a statutory business trust created
under the laws of the State of Delaware (the "Trust"), hereby certifies that
______________ (the "Holder") is the registered owner of $28,750,000 in
aggregate liquidation amount of Preferred Securities of the Trust specified in
Schedule A hereto representing undivided beneficial interests in the assets of
the Trust designated the 9.20% Cumulative Trust Preferred Securities
(liquidation amount $25 per Preferred Security) (the "Preferred Securities").
The Preferred Securities are transferable on the books and records of the Trust,
in person or by a duly authorized attorney, upon surrender of this certificate
duly endorsed and in proper form for transfer. The designation, rights,
privileges, restrictions, preferences and other terms and provisions of the
Preferred Securities represented hereby are issued and shall in all respects be
subject to the provisions of the Amended and
<PAGE>

Restated Declaration of Trust of the Trust dated as of March 21, 2001, as the
same may be amended from time to time (the "Declaration"), including the
designation of the terms of the Preferred Securities as set forth in Annex I to
the Declaration. Capitalized terms used but not defined herein shall have the
meaning given them in the Declaration. The Sponsor will provide a copy of the
Declaration, the Preferred Securities Guarantee, the Common Securities Guarantee
(as may be appropriate), and the Indenture (including any supplemental
indenture) to a Holder without charge upon written request to the Trust at its
principal place of business.

     Upon receipt of this certificate, the Holder is bound by the Declaration
and is entitled to the benefits thereunder and to the benefits of the Preferred
Securities Guarantee to the extent provided therein.

     By acceptance, the Holder agrees to treat, for United States Federal income
tax purposes, the Debentures as indebtedness and the Preferred Securities as
evidence of indirect beneficial ownership in the Debentures.
<PAGE>

     IN WITNESS WHEREOF, the Trust has duly executed this certificate.

Dated:  March 21, 2001
                              STERLING BANCSHARES CAPITAL TRUST II

                                              /s/ George Martinez
                              By: ______________________________________________
                                              George Martinez
                                              Administrative Trustee

                PROPERTY TRUSTEE'S CERTIFICATE OF AUTHENTICATION

This is one of the Preferred Securities referred to in the within-mentioned
Declaration.

                                              BANKERS TRUST COMPANY,
                                              as Property Trustee

                                                   /s/  SUSAN JOHNSON
                                              By: ______________________________
                                              Authorized Signatory
<PAGE>

     Distributions payable on each Preferred Security will be fixed at a rate
per annum of 9.20% (the "Coupon Rate") of the liquidation amount of $25 per
Preferred Security, such rate being the rate of interest payable on the
Debentures to be held by the Property Trustee.  Distributions in arrears for
more than one quarterly period will bear interest thereon compounded quarterly
at the Coupon Rate (to the extent permitted by applicable law).  A Distribution
is payable only to the extent that payments are made in respect of the
Debentures held by the Property Trustee and to the extent the Property Trustee
has funds on hand legally available therefor.

     Distributions on the Preferred Securities will be cumulative, will
accumulate from the most recent date to which Distributions have been paid or,
if no Distributions have been paid, from March 21, 2001 will be payable
quarterly in arrears, on March 31, June 30, September 30 and December 31 of each
year, commencing on June 30, 2001, except as otherwise described below and on
the Stated Maturity Date. Distributions will be computed on the basis of a 360-
day year consisting of twelve 30-day months and, for any period less than a full
calendar month, the number of days elapsed in such month.  As long as no Event
of Default has occurred and is continuing under the Indenture, the Debenture
Issuer has the right under the Indenture to defer payments of interest by
extending the interest payment period at any time and from time to time on the
Debentures for a period not exceeding 20 consecutive calendar quarterly periods,
including the first such quarterly period during such extension period (each an
"Extension Period"), provided that no Extension Period shall end on a date other
than an Interest Payment Date for the Debentures or extend beyond the Stated
Maturity Date of the Debentures.  As a consequence of such deferral,
Distributions will also be deferred.  Despite such deferral, quarterly
Distributions will continue to accumulate with interest thereon (to the extent
permitted by applicable law, but not at a rate exceeding the rate of interest
then accruing on the Debentures) at the Coupon Rate compounded quarterly during
any such Extension Period.  Prior to the termination of any such Extension
Period, the Debenture Issuer may further defer payments of interest by further
extending such Extension Period; provided that such Extension Period, together
with all such previous and further extensions within such Extension Period, may
not exceed 20 consecutive quarterly periods, including the first quarterly
period during such Extension Period, end on a date other than an Interest
Payment Date for the Debentures or extend beyond the Stated Maturity Date of the
Debentures. Payments of accumulated Distributions will be payable to Holders as
they appear on the books and records of the Trust on the first record date after
the end of the Extension Period.  Upon the termination of any Extension Period
and the payment of all amounts then due, the Debenture Issuer may commence a new
Extension Period, subject to the above requirements.

     Subject to the prior approval of the Federal Reserve Board if such approval
is then required under applicable law or capital guidelines or policies of the
Federal Reserve Board and the receipt of any other required regulatory approvals
and to certain other conditions set forth in the Declaration and the Indenture,
the Property Trustee may, at the direction of the Sponsor, at any time liquidate
the Trust and cause the Debentures to be distributed to the holders of the
Securities in liquidation of the Trust or, simultaneously with any redemption of
the Debentures, cause a Like Amount of the Securities to be redeemed by the
Trust.

     The Preferred Securities shall be redeemable as provided in the
Declaration.
<PAGE>

                                   ASSIGNMENT
FOR VALUE RECEIVED, the undersigned assigns and transfers this Preferred
Security Certificate to:

________________________________________________________________________________

________________________________________________________________________________

________________________________________________________________________________
        (Insert assignee's social security or tax identification number)

________________________________________________________________________________

________________________________________________________________________________

________________________________________________________________________________

________________________________________________________________________________
                   (Insert address and zip code of assignee)

and irrevocably appoints _______________________________________________________

________________________________________________________________________________

____________________________ agent to transfer this Preferred Security
Certificate on the books of the Trust.  The agent may substitute another to act
for him or her.

Date: _______________________

Signature: __________________ (Sign exactly as your name appears on the other
side of this Preferred Security Certificate)

Signature Guarantee ***:  ___________________________________

____________________
***   Signature must be guaranteed by an "eligible guarantor institution" that
is a bank, stockbroker, savings and loan association or credit union meeting the
requirements of the Registrar, which requirements include membership or
participation in the Securities Transfer Agents Medallion Program ("STAMP") or
such other "signature guarantee program" as may be determined by the Registrar
in addition to, or in substitution for, STAMP, all in accordance with the
Securities and Exchange Act of 1934, as amended.
<PAGE>

                                   Schedule A

     The initial number of Preferred Securities evidenced by the Certificate to
which this Schedule is attached is 1,150,000 (having an aggregate liquidation
amount of $28,750,000).  The notations in the following table evidence decreases
and increases in the number of Preferred Securities evidenced by such
certificate.

<TABLE>
<CAPTION>
                                                     Number of Preferred
    Decrease in              Increase in                  Securities
     Number of                Number of                Remaining After
     Preferred                Preferred                 such Decrease               Notation by
    Securities               Securities                  or Increase                 Registrar
-----------------------------------------------------------------------------------------------------
<S>                          <C>                     <C>                            <C>

-----------------------------------------------------------------------------------------------------
</TABLE>

Source: [{"source": "alea-institute/alea-institute/kl3m-data-edgar-agreements/train-00021-of-00352.parquet"}, [{"source": "alea-institute/alea-institute/kl3m-data-edgar-agreements/train-00021-of-00352.parquet"}]]