1
                                                                     EXHIBIT 4.4



- --------------------------------------------------------------------------------



                                WARRANT AGREEMENT


                                     BETWEEN


                                ADMINISTAFF, INC.


                                       AND


             AMERICAN EXPRESS TRAVEL RELATED SERVICES COMPANY, INC.







                           Dated as of March 10, 1998





- --------------------------------------------------------------------------------



   2



                                WARRANT AGREEMENT


         THIS WARRANT AGREEMENT is made as of March 10, 1998, by and between
ADMINISTAFF, INC., a Delaware corporation (the "Company"), and AMERICAN EXPRESS
TRAVEL RELATED SERVICES COMPANY, INC., a New York corporation (the "Purchaser").

                                    RECITALS:

     A. The Company and the Purchaser have entered into a Securities Purchase
Agreement dated as of January 27, 1998 (the "Purchase Agreement"), pursuant to
which the Purchaser has agreed to purchase from the Company 693,126 Units (as
hereinafter defined), each of which shall consist of one share of Common Stock
(as hereinafter defined) and 2.98 Warrants (as hereinafter defined).

     B. The Company and the Purchaser have agreed to enter into this Agreement
to supplement the terms and conditions set forth in the Purchase Agreement which
relate to the Warrants purchased thereunder.

     NOW, THEREFORE, the parties hereto agree as follows:

          SECTION 1. Definitions.

          (a) Certain Definitions. For the purposes of this Agreement, the
following terms have the meanings set forth below:

          "Affiliate" has the same meaning as in Rule 12b-2 promulgated under
the Exchange Act.

          "Business Day" means any day which is neither a Saturday or Sunday nor
a legal holiday on which banks are authorized or required to be closed in New
York, New York or Houston, Texas.

          "Change of Control" means the occurrence of any of the following: (a)
any third party shall have acquired beneficial ownership of more than 30% of the
outstanding voting stock of the Company (within the meaning of Section 13(d) or
14(d) of the Exchange Act); or (b) individuals who on the Closing Date were
directors of the Company (together with any replacement or additional directors
who were nominated or elected by a majority of directors then in office) cease
to constitute a majority of the Board of Directors of the Company.

          "Closing Date" means March 10, the date of the Closing of the purchase
by the Purchaser of the Units in accordance with the Purchase Agreement.


          
   3



          "Common Stock" means shares now or hereafter authorized of any class
of common stock of the Company and any other class of capital stock of the
Company, however designated, that has the right (subject to any prior rights of
any class or series of preferred stock) to participate in any distribution of
the assets upon voluntary or involuntary liquidation, dissolution or winding up
of the Company or in the earnings of the Company without limit as to per share
amount, and shall include, without limitation, the presently authorized
60,000,000 shares of Common Stock, par value $0.01 per share.

          "Company" is defined in the Preamble.

          "Exchange Act" means the Securities Exchange Act of 1934, as amended.

          "Expiration Date" is defined in the Warrant Certificates.

          "Exercise Price" means the exercise price per Warrant as set forth in
the Warrant Certificate evidencing such Warrant and as adjusted from time to
time in accordance with this Agreement.

          "Fair Market Value per Share" means the arithmetic mean of the closing
sales price of a share of Common Stock of the Company as reported by the New
York Stock Exchange Composite Transactions over the five trading days
immediately preceding the date of determination or, if not so trading, the fair
value as determined in good faith by the Board of Directors of the Company.

          "GAAP" means generally accepted accounting principles in effect from
time to time in the United States.

          "Governmental Authority" means any nation or government, any state or
other political subdivision thereof and any entity exercising executive,
legislative, judicial, regulatory or administrative functions of or pertaining
to government.

          "Holder" means the Purchaser or any subsequent holder of Warrants or
Warrant Stock, to which the Warrants or Warrant Stock are transferred in
accordance with the provisions of this Agreement and the Purchase Agreement.

          "Marketing Agreement" means the Marketing Agreement, dated as of the
date hereof, by and between the Company and the Purchaser in substantially the
form of Exhibit A attached to the Purchase Agreement.

          "Person" means any natural person, corporation, partnership, limited
liability company, firm, association or any other entity, whether acting in an
individual, fiduciary or other capacity.

          "Purchase Agreement" is defined in the Recitals.



                                       -2-

   4




          "Put Closing" is defined in Section 5(a).

          "Put Exercise Notice" is defined in Section 5(a).

          "Put Price" is defined in Section 5(a).

          "Put Right" is defined in Section 5(a).

          "Registration Rights Agreement" means the Registration Rights
Agreement, dated as of the date hereof, between the Company and the Purchaser,
in substantially the form of Exhibit B attached to the Purchase Agreement.

          "SEC" means the Securities and Exchange Commission.

          "Securities Act" means the Securities Act of 1933, as amended.

          "Unit" means an investment unit consisting of one share of Common
Stock and 2.98 Warrants.

          "Warrant Certificates" means collectively, the certificates evidencing
(i) the Warrants with an Expiration Date of the third anniversary of the Closing
Date in the form of Exhibit A-1 attached hereto, (ii) the Warrants with an
Expiration Date of the fourth anniversary of the Closing Date in the form of
Exhibit A-2 attached hereto, (iii) the Warrants with an Expiration Date of the
fifth anniversary of the Closing Date in the form of Exhibit A-3 attached
hereto, (iv) the Warrants with an Expiration Date of the sixth anniversary of
the Closing Date in the form of Exhibit A-4 attached hereto, (v) the Warrants
with an Expiration Date of the seventh anniversary of the Closing Date in the
form of Exhibit A-5 attached hereto.

          "Warrant Stock" means the securities which a Holder may acquire upon
exercise of a Warrant, together with any other securities which such Holder may
be issued in respect of any such securities, including, without limitation, by
way of any dividend or other distribution on such securities, any split-up of
such securities or a recapitalization, merger, consolidation, share exchange,
reorganization or other transaction or series of related transactions in which
shares of such securities are changed into or exchanged for securities of
another corporation.

          "Warrants" means the 2,065,515 warrants each of which entitles the
holder thereof to purchase one share of Common Stock of the Company issued to
the Purchaser on the Closing Date pursuant to this Agreement and the Purchase
Agreement, which warrants shall be subject to adjustment and shall have the
rights, privileges and limitations set forth in this Agreement and in each
Warrant.



                                       -3-

   5



          (b) Terms Defined in Purchase Agreement. Unless otherwise defined
herein, capitalized terms used in this Agreement shall have the meanings
ascribed to such terms in the Purchase Agreement.

          SECTION 2. Exercise of Warrants.

          (a) A Warrant may be exercised by the Purchaser or any Holder only in
accordance with the terms and conditions of this Agreement and at any time
during the period beginning on the date hereof and ending on the Expiration Date
for such Warrant as set forth in the Warrant Certificate evidencing such
Warrant. The Warrant Certificates evidencing the Warrants issued to the
Purchaser on the Closing Date shall be identical except for the Expiration Date
and the Exercise Price. The Expiration Date for the Warrants shall be as
follows: the third anniversary of the Closing Date for 400,000 Warrants; the
fourth anniversary of the Closing Date for 400,000 Warrants; the fifth
anniversary of the Closing Date for 400,000 Warrants; the sixth anniversary of
the Closing Date for 400,000 Warrants; and the seventh anniversary of the
Closing Date for 465,515 Warrants. The Exercise Price for the Warrants shall be
as follows: $40 for the Warrants expiring on the third anniversary of the
Closing Date; $50 for the Warrants expiring on the fourth anniversary of the
Closing Date; $60 for the Warrants expiring on the fifth anniversary of the
Closing Date; $70 for the Warrants expiring on the sixth anniversary of the
Closing Date; and $80 for the Warrants expiring on the seventh anniversary of
the Closing Date.

          (b) Subject to the terms and conditions hereof, Warrants may be
exercised pursuant to this Section 2 upon surrender to the Company at its office
designated for such purpose (the address of which is set forth in Section 13) of
the certificate or certificates evidencing the Warrant(s) to be exercised and
upon payment to the Company of the aggregate Exercise Price for the number of
Warrants which are then exercised, provided that a Warrant may not be exercised
in part. Upon such surrender of Warrant Certificates and payment of the Exercise
Price in cash or by check payable to the Company, the Company shall issue and
cause to be delivered with all reasonable dispatch (and in any event within
three Business Days after such surrender) to or upon the written order of the
Holder, and in the name of the Holder or the Holder's nominee, a certificate or
certificates for the number of full shares of Warrant Stock issuable upon the
exercise of such Warrants, together with such other property (including cash)
and securities as may then be deliverable upon such exercise, including cash for
fractional Warrant Stock as provided in Section 11, provided that all such
Warrant Stock held by the Purchaser shall be subject to the restrictions set
forth in Sections 7 and 8 of the Purchase Agreement. Such certificate or
certificates shall be deemed to have been issued and the Person so named therein
shall be deemed to have become a holder of record of such Warrant Stock as of
the date of the surrender of such Warrant Certificates.




                                       -4-

   6



          (c) Subject to the terms and conditions hereof, the Warrants shall be
exercisable at the election of the Holders thereof, either in full or from time
to time in part (but in no event shall a Warrant be exercisable in part), and in
the event that a Warrant Certificate is exercised in respect of fewer than all
of the Warrants evidenced by such Warrant Certificate at any time prior to the
Expiration Date of such Warrant, a new Warrant Certificate evidencing the
remaining Warrant or Warrants will be issued and delivered pursuant to the
provisions of this Section 2(c). All Warrant Certificates surrendered upon
exercise of Warrants shall be canceled. The Company shall keep copies of this
Agreement and any notices received hereunder available for inspection during
normal business hours at its office. The Company will furnish, at its expense,
copies of this Agreement and all such notices, upon request, to any Holder of
any Warrant Certificates.

          SECTION 3. Adjustment of Exercise Price and Number of Shares of
Warrant Stock Issuable. The Exercise Price and the number of shares of Warrant
Stock issuable upon the exercise of each Warrant are subject to adjustment from
time to time upon the occurrence of any of the events enumerated in this Section
3.

          (a) Adjustment for Change in Capital Stock of the Company. If the
Company (i) pays a dividend or makes a distribution on its Common Stock in
shares of any class of its capital stock, (ii) subdivides its outstanding shares
of Common Stock into a greater number of shares, (iii) combines its outstanding
shares of Common Stock into a smaller number of shares, (iv) makes a
distribution on its Common Stock in shares of its capital stock other than
Common Stock, or (v) issues to holders of its Common Stock by reclassification
of its Common Stock any shares of its capital stock, then the Exercise Price and
number of shares for which any Warrant may be exercised in effect immediately
prior to such action shall be proportionately adjusted so that the Holder of the
Warrant thereafter exercised may receive the aggregate number and kind of shares
of capital stock of the Company which it would have owned immediately following
such action if such Warrant had been exercised immediately prior to such action.
Such adjustment shall be made successively whenever any event listed above shall
occur, and shall become effective immediately after the record date in the case
of a dividend or distribution and immediately after the effective date in the
case of a subdivision, combination or reclassification. If after an adjustment
made pursuant to the second preceding sentence a Holder of a Warrant upon
exercise of such Warrant may receive shares of two or more classes of capital
stock of the Company, the Board of Directors of the Company shall determine in
the good faith exercise of its reasonable business judgment the allocation of
the adjusted Exercise Price between the classes of capital stock. After such
allocation, the exercise privilege and the Exercise Price of each class of
capital stock shall thereafter be subject to adjustment on terms comparable to
those in this Section 3.

          (b) Reorganization of the Company. In the event of any capital
reorganization, recapitalization or reclassification of the capital stock of the
Company, or consolidation or merger of the Company with another entity, in which
the Company does not continue as the surviving corporation or, if it does so
continue, its Common Stock does not remain outstanding, any acquisition of
capital stock of the Company by means of a share exchange, or the sale, lease,
transfer, conveyance or other disposition of all or substantially all of its
assets to another entity, then, as a



                                       -5-

   7



condition of and concurrently with such reorganization, recapitalization,
reclassification, consolidation, merger, share exchange or sale, lease,
transfer, conveyance or other disposition, lawful and adequate provision shall
be made whereby the Holders of the Warrant Certificates shall thereafter have
the right to purchase and receive, on the basis and upon the terms and
conditions specified in this Agreement and in lieu of the Warrant Stock
immediately theretofore purchasable and receivable upon the exercise of the
rights represented by the Warrants, such shares of stock, securities, cash or
property as would have been issued or payable with respect to or in exchange for
the number of shares of Warrant Stock purchasable and receivable immediately
prior to such transaction upon the exercise of the rights represented by the
Warrant Certificates if such Warrants had been exercised immediately prior to
such transaction. If such consolidation, merger, share exchange, sale, lease,
transfer, conveyance or other disposition is with any Person or group of Persons
(within the meaning of Section 13(d) or 14(d) of the Exchange Act) who shall
have made a purchase, tender or exchange offer pursuant to which a majority of
the outstanding shares of Common Stock of the Company were validly tendered and
accepted, promptly after the consummation of such transaction, the Holders of
the Warrants shall be given a reasonable opportunity (and, in no event, less
than 30 days) to elect to receive the stock, securities, cash or property issued
or paid (or to be issued or paid) to holders of the Common Stock in accordance
with such offer. In any such case appropriate provision shall be made with
respect to the rights and interests of the Holders of the Warrants to the end
that the provisions of this Agreement (including, without limitation, provisions
for adjustment of the Exercise Price and of the number and type of securities
purchasable upon the exercise of the Warrants) shall thereafter be applicable,
as nearly as may be, in relation to any shares of stock, securities, cash or
property thereafter deliverable upon the exercise of the Warrants. The Company
shall not effect any such consolidation, merger, share exchange or sale, lease,
transfer, conveyance or other disposition unless prior to or simultaneously with
the consummation thereof the successor entity (if other than the Company)
resulting from such consolidation, merger or share exchange or the entity
purchasing or otherwise acquiring such assets or shares (i) shall assume by a
supplemental Warrant Agreement, reasonably satisfactory in form, scope and
substance to the Holders (which shall be mailed or delivered to the Holders of
the Warrants at the last address of such Holders appearing on the books of the
Company) the obligation to deliver to such Holders such shares of stock,
securities, cash or property as, in accordance with the foregoing provisions,
such Holders may be entitled to purchase (the "Substitute Securities") and (ii)
shall assume all of the other obligations of the Company set forth in this
Agreement, the Purchase Agreement and the Registration Rights Agreement.
Following such assumption such obligations shall apply to the Substitute
Securities rather than to the Warrant Stock. If the issuer of securities
deliverable upon exercise of Warrants under the supplemental Warrant Agreement
is an Affiliate of the formed, surviving, transferee or lessee entity, such
issuer shall join the supplemental Warrant Agreement. The foregoing provisions
of this paragraph shall similarly apply to successive reorganizations,
recapitalizations, reclassifications, consolidations, mergers, share exchanges,
sales, leases, transfers, conveyances or other dispositions.




                                       -6-

   8



          SECTION 4. Covenants.

          (a) Private Company Information. If the Company shall cease to be
subject to the periodic reporting obligations of the Exchange Act and for so
long as the Purchaser's Interest is at least five percent, the Company will
furnish, or will cause to be furnished, to each Holder copies of the following
financial statements, reports and information:

                    (i) promptly when available and in any event within 90 days
          after the close of each Fiscal Year, a consolidated balance sheet at
          the close of such Fiscal Year, and related consolidated statements of
          operations, stockholders' equity and cash flows for such Fiscal Year,
          of the Company and the Company Subsidiaries (with comparable
          information at the close of and for the prior Fiscal Year), certified
          (in the case of consolidated statements) without qualification by
          Ernst & Young or other nationally recognized independent public
          accountants; and

                    (ii) promptly when available and in any event within 45 days
          after the close of each Fiscal Quarter, consolidated balance sheets at
          the close of such Fiscal Quarter, and consolidated statements of
          operations, stockholders' equity and cash flows for such Fiscal
          Quarter and for the period commencing at the close of the previous
          Fiscal Year and ending with the close of such Fiscal Quarter, of the
          Company and the Company Subsidiaries (with comparable information at
          the close of and for the corresponding Fiscal Quarter of the prior
          Fiscal Year and for the corresponding portion of such prior Fiscal
          Year), certified by the chief financial or executive officer of the
          Company.

          (b) Public Company Information. So long as the Company is subject to
the periodic reporting requirements of the Exchange Act and for so long as the
Purchaser's Interest is at least five percent, the Company will:

                    (i) file with the SEC on or before the required date all
          regular or periodic reports required pursuant to the Exchange Act; and

                    (ii) use its reasonable commercial efforts to make publicly
          available information concerning the Company sufficient to allow a
          Holder to dispose in accordance with this Agreement and the Warrant
          Agreement of all or a portion of the Warrant Stock pursuant to Rule
          144 (or any successor provision) promulgated by the SEC under the
          Securities Act.

          (c) Inconsistent Agreements. The Company will not, and will not permit
any Company Subsidiary to, take any action which would (i) impair or adversely
affect the right of a Holder to exercise the Warrants or (ii) breach any of the
covenants or agreements in this document.




                                       -7-

   9


          (d) Governmental Approvals. The Company will use its reasonable
commercial efforts, and will cooperate with the Holders to, secure all necessary
consents, approvals, authorizations and exemptions from all Governmental
Authorities in connection with the transactions contemplated hereby and the
exercise of the Warrants and the issuance of shares of Common Stock upon
exercise of the Warrants.

          (e) Termination of Rights upon Sale to the Public. Notwithstanding
anything to the contrary set forth herein, the obligations of the Company set
forth in this Section 4 shall terminate with respect to any Holder (including an
underwriter) acquiring any Warrants or Warrant Stock pursuant to a registration
statement declared effective by the SEC under the Securities Act or in a sale
effected pursuant to Rule 144 promulgated under the Securities Act.

          SECTION 5. Restrictions on Transfers.

          (a) Transfers of Warrants.

                    (i) Without the prior written consent of the Company, the
          Purchaser may not dispose of or transfer any Warrants now or hereafter
          owned, whether by sale, assignment, gift, pledge, encumbrance or
          otherwise, except (A) to a Subsidiary of the Purchaser or to any
          entity of which the Purchaser is, directly or indirectly, a Subsidiary
          (provided that such transferee agrees to be bound by the transfer
          restrictions contained herein), (B) in connection with the exercise of
          a Warrant in accordance with the provisions of the Agreement and (C)
          in connection with the exercise in accordance with Section 5(a)(ii) of
          a put of a Warrant to the Company after the occurrence of a Change of
          Control.

                    (ii) Upon a Change of Control, each of the Purchaser and any
          other Holders to which the Warrants were transferred in accordance
          with Section 5(a) hereof shall individually have the right (the "Put
          Right") to require the Company to purchase all (but not less than all)
          of the Warrants owned by the Purchaser and each such Holder. The
          Company shall notify each Holder in writing, as promptly as
          practicable, but in any event within three Business Days, after a
          Change in Control. The Put Right may be exercised by the Purchaser and
          any Holder by delivering a written notice, which notice shall be
          irrevocable (the "Put Exercise Notice"), to the Company within 90 days
          after any Change of Control. The purchase price for each Warrant
          purchased by the Company upon exercise of the Put Right shall equal
          the Fair Market Value per Share as of the date of the Change of
          Control minus the Exercise Price of such Warrant (the "Put Price").
          The purchase and sale of the Warrants upon exercise of the Put Rights
          shall be consummated at a closing (the "Put Closing") that shall occur
          not later than 15 days following the Put Exercise Notice. At the Put
          Closing, the Purchaser and the Holders seeking to exercise the Put
          Rights set forth herein shall surrender to the Company the Warrant
          Certificates evidencing their Warrants. In exchange therefor, (A) if
          the Put Price for the Warrants evidenced




                                       -8-

   10



          by a Warrant Certificate is greater than zero, the Company shall issue
          to the Holder of such Warrants Common Stock in an amount, calculated
          based on the Fair Market Value per Share of such Common Stock at the
          time of Change of Control, equal to the Put Price for such Warrants
          multiplied by the number of Warrants evidenced by such Warrant
          Certificate and (B) if the Put Price for the Warrants evidenced by a
          Warrant Certificate is not greater than zero, the Company shall not be
          obligated to make any payment or issue any Common Stock to the Holder
          of such Warrants. Prior to the delivery of a Put Exercise Notice, the
          Put Right shall not restrict or limit or have any affect on a Holder's
          right to exercise a Warrant pursuant to Section 2 hereof. If as a
          result of a Change in Control the Company is not the surviving entity
          or shares of Common Stock are no longer outstanding after a Change in
          Control, then the Put Price shall be payable in such shares of stock,
          securities, cash or property as would have been issued or payable as a
          result of such Change of Control with respect to or in exchange for
          the number of shares of Common Stock a Holder would have received upon
          exercise of the Put immediately prior to such Change in Control.

          (b) Restricted Securities. Warrants are transferable only in
accordance with Section 5(a).

          (c) Transfers of Warrant Stock. The Purchaser may not dispose of or
transfer any Warrant Stock now or hereafter owned, whether by sale, assignment,
gift, pledge, encumbrance or otherwise, except in accordance with Section 8 of
the Purchase Agreement.

          SECTION 6. Termination.

          This Agreement shall terminate on the earlier of (a) the seventh
anniversary of the Closing Date and (b) the exercise or expiration of all
Warrants issued pursuant to this Agreement. Each Warrant shall expire upon the
Expiration Date set forth in the Warrant Certificate by which it is evidenced.

          SECTION 7. Registration of Transfers and Exchanges.

          (a) The Company shall from time to time register the transfer of any
outstanding Warrant Certificates made in accordance with Section 5 hereof in a
Warrant register to be maintained by the Company upon surrender of such Warrant
Certificates accompanied by a written instrument or instruments of transfer in
form reasonably satisfactory to the Company, duly executed by the Holder or
Holders thereof or by the duly appointed legal representative thereof or by a
duly authorized attorney; provided, however, that prior to effecting such
transfer, the transferee shall agree (in a form reasonably satisfactory to the
Company) to be bound by the terms of this Agreement. Upon any such registration
of transfer, a new Warrant Certificate shall be issued to the transferee(s) and
the surrendered Warrant Certificate shall be canceled. Until the Warrant
Certificate is transferred on the Warrant register of the Company, the Company
may treat the Holder as shown in the Warrant register as the absolute owner of
the Warrant Certificate for all purposes, and


                                       -9-

   11


notwithstanding any notice to the contrary. The Company agrees that it will make
the Warrant register available for inspection by the Holders for a proper
purpose during normal business hours at its office.

          (b) The Holders agree that each Warrant Certificate and each
certificate representing Warrant Stock will bear the following legend (the
"Securities Legend"):

                    "THE SECURITIES REPRESENTED BY THIS CERTIFICATE HAVE NOT
                    BEEN REGISTERED UNDER THE SECURITIES ACT OF 1933, AS
                    AMENDED, OR ANY STATE SECURITIES LAWS. SAID SECURITIES MAY
                    NOT BE SOLD OR TRANSFERRED IN THE ABSENCE OF SUCH
                    REGISTRATION OR AN EXEMPTION FROM THE REGISTRATION
                    PROVISIONS OF SAID ACT OR LAWS. THE SECURITIES REPRESENTED
                    BY THIS CERTIFICATE ARE SUBJECT TO THE TERMS OF A SECURITIES
                    PURCHASE AGREEMENT, DATED AS OF JANUARY 27, 1998, BETWEEN
                    ADMINISTAFF, INC. (THE "COMPANY") AND AMERICAN EXPRESS
                    TRAVEL RELATED SERVICES COMPANY, INC. (THE "PURCHASER"), A
                    WARRANT AGREEMENT DATED AS OF MARCH __ 1998, BETWEEN THE
                    COMPANY AND THE PURCHASER, AND A REGISTRATION RIGHTS
                    AGREEMENT, DATED AS OF MARCH __ 1998, BETWEEN THE COMPANY
                    AND THE PURCHASER, COPIES OF EACH OF WHICH ARE ON FILE AT
                    THE MAIN OFFICE OF THE COMPANY. ANY SALE OR TRANSFER OF THE
                    SECURITIES EVIDENCED BY THIS CERTIFICATE IS SUBJECT TO THE
                    TERMS OF THOSE AGREEMENTS AND ANY SALE OR TRANSFER OF SUCH
                    SECURITIES IN VIOLATION OF SAID AGREEMENTS SHALL BE
                    INVALID."

          (c) If the holder of the Warrants or Warrant Stock delivers, in
accordance with Section 8(e) of the Purchase Agreement, to the Company an
opinion of King & Spalding or such other counsel that no subsequent transfer of
such Warrants or Warrant Stock shall require registration under the Securities
Act, the Company shall promptly upon such contemplated transfer deliver new
certificates for such Warrants or Warrant Stock which do not bear the Securities
Legend; 



                                      -10-

   12




provided, however, that if at such time, any such Warrants or Warrant Stock
remain subject to certain provisions of this Agreement or the Purchase
Agreement, the Company shall not remove the Securities Legend, but shall modify
it to delete all references to restrictions or conditions on sale of Warrants or
Warrant Stock except those references to restrictions or conditions which are
specified in this Agreement or the Purchase Agreement. If the Company is not
required to deliver new certificates for such Warrants or Warrant Stock not
bearing such legend, the holder thereof shall not transfer the same until the
prospective transferee has confirmed to the Company in writing its agreement to
be bound by the conditions contained in Section 5(b) hereof with respect to
Warrants and Section 8(b) of the Purchase Agreement with respect to Warrant
Stock.

          (d) If any Warrants or Warrant Stock are or become eligible for sale
pursuant to Rule 144(k), the Company, upon the request of holders of any such
Warrants or Warrant Stock, shall remove the Securities Legend from the
certificates for such Warrants or Warrant Stock; provided, however, that if at
such time, any such Warrants or Warrant Stock remain subject to certain
provisions of this Agreement or the Purchase Agreement, the Company shall not
remove the Securities Legend, but shall modify it to delete all references to
restrictions or conditions on sale of the Warrants or Warrant Stock except those
references to restrictions or conditions which are still applicable and
specified in this Agreement or the Purchase Agreement.

          (e) Warrant Certificates may be exchanged at the option of the
Holder(s) thereof when surrendered to the Company at its office for another
Warrant Certificate or other Warrant Certificates of like tenor and representing
in the aggregate a like number of Warrants, including, without limitation, upon
an adjustment in the Exercise Price or in the number of Warrant Shares
purchasable upon exercise of the Warrants. Warrant Certificates surrendered for
exchange shall be canceled.

          SECTION 8. Payment of Taxes. The Company will pay all stamp, transfer
and similar taxes in connection with the issuance, sale and delivery of the
Warrants hereunder, as well as all such taxes attributable to the initial
issuance of Warrant Stock upon the exercise of Warrants and payment of the
appropriate Exercise Price. The Company will not, however, be required to pay
any such taxes imposed in connection with any transfer of any Warrants or
Warrant Stock or any federal or state income taxes payable in respect of any
Holder's purchase, ownership, sale, transfer, exercise or other disposition of
Warrants or Warrant Stock.

          SECTION 9. Mutilated or Missing Warrant Certificates. Upon receipt by
the Company of evidence reasonably satisfactory to the Company (which shall
include an affidavit of the Holder) that any Warrant Certificate shall have been
mutilated, lost, stolen or destroyed and, in the case of loss, theft or
destruction, a customary indemnity agreement from the Holder of such Warrant
Certificate, the Company shall issue, in exchange and substitution for and upon
cancellation of the mutilated Warrant Certificate, or in lieu of and
substitution for the Warrant Certificate lost, stolen or destroyed, a new
Warrant Certificate of like tenor and representing an equivalent number of
Warrants.



                                      -11-

   13




          SECTION 10. Reservation of Warrant Stock. The Company will at all
times that any Warrant is exercisable reserve and keep available, free from
preemptive or similar rights, out of the aggregate of its authorized but
unissued capital stock or its authorized and issued capital stock held in its
treasury, for the purpose of enabling it to satisfy any obligation to issue
Warrant Stock upon exercise of Warrants, the maximum number of shares of each
class of capital stock constituting a part of the Warrant Stock which may then
be deliverable upon the exercise of all outstanding Warrants. The Company or, if
appointed, the transfer agent for shares of each class of capital stock of the
Company (the "Transfer Agent") and every subsequent transfer agent for any
shares of the Company's capital stock issuable upon the exercise of the Warrants
will be irrevocably authorized and directed at all times to reserve such number
of authorized shares as shall be required for such purpose. The Company will
keep a copy of this Agreement on file with the Transfer Agent and with every
subsequent transfer agent for any shares of the Company's capital stock issuable
upon the exercise of the rights of purchase represented by the Warrants. The
Company will furnish such Transfer Agent a copy of all notices of adjustments,
and certificates related thereto, transmitted to Holders pursuant to Section 12.
Before taking any action which would cause an adjustment pursuant to Section 3
to the maximum number of shares of Warrant Stock deliverable upon the exercise
of all outstanding Warrants pursuant to Section 2(a), the Company shall cause to
be authorized additional shares of Common Stock such that the sum of such
maximum number of shares of Common Stock deliverable upon exercise of all
outstanding Warrants and the number of shares of Common Stock outstanding or
issuable pursuant to outstanding rights, options or warrants as of such date
does not exceed the number of shares of Common Stock authorized pursuant to the
Company's Certificate.

          SECTION 11. Fractional Interests. The Company shall not be required to
issue fractional shares of Warrant Stock on the exercise of Warrants. If more
than one Warrant shall be presented for exercise in full at the same time by the
same Holder, the number of full shares of Warrant Stock which shall be issuable
upon exercise thereof shall be computed on the basis of the aggregate number of
shares of Warrant Stock purchasable on exercise of the Warrants so presented. If
any fraction of a share of the Warrant Stock would, except for the provisions of
this Section 11, be issuable on the exercise of any Warrants (or specified
portion thereof), the Company shall pay an amount in cash equal to the Fair
Market Value per Share calculated as of the day immediately preceding the date
the Warrant is presented for exercise, multiplied by such fraction.

          SECTION 12. Notice to Warrant Holders. Upon any adjustment of the
Exercise Price or number or type of securities purchasable upon exercise of the
Warrants pursuant to Section 3, the Company shall promptly thereafter (i) cause
to be filed with the Company a certificate of the chief financial officer of the
Company setting forth the Exercise Price and the number and type of securities
or other property constituting Warrant Stock after such adjustment and setting
forth in reasonable detail the method of calculation and the facts upon which
such calculations are based and, in the case of an adjustment pursuant to
Section 3(b), setting forth the number and type of securities or other property
constituting Warrant Stock (or portion thereof) issuable, after such adjustment
in the Exercise Price or number of Warrant Stock, upon exercise of a Warrant and
payment of the adjusted Exercise Price, and (ii) cause to be given to each of
the Holders of the Warrant Certificates





                                      -12-

   14



written notice of such adjustments, together with a copy of such certificate.
Where appropriate, such notice may be given in advance and included as a part of
the notice required to be given under the other provisions of this Section 11.
In the event:

          (a) the Company shall authorize the payment of any dividend or
distribution to holders of shares of Common Stock of capital stock of the
Company; or

          (b) of any capital reorganization, reclassification, recapitalization,
consolidation, or share exchange, or sale, lease, conveyance, transfer or other
disposition to which the adjustment provisions of Section 3(b) apply, or a
purchase, tender or exchange offer for shares of Common Stock or other
securities constituting part of the Warrant Stock (whether by the Company or
some other party); or

          (c) of the voluntary or involuntary dissolution, liquidation or
winding up of the Company; or

          (d) the Company proposes to take any action that would require an
adjustment of the Exercise Price or number of shares of Warrant Stock for which
the Warrants are exercisable;

then the Company shall cause to be given to each of the Holders, at least 20
days prior to the applicable record date hereinafter specified (or promptly in
the case of events for which there is no record date), a written notice stating
(as applicable) (i) the date as of which the holders of record of shares of
Common Stock entitled to receive any such dividends or distribution are to be
determined, (ii) the date on which any such reclassification, recapitalization
or reorganization, consolidation, merger, share exchange, sale, lease,
conveyance, transfer or disposition to which the adjustment provisions of
Section 3(b) apply or any such dissolution, liquidation or winding up is
expected to become effective or be consummated, or (iii) the initial expiration
date set forth in any purchase, tender or exchange offer for shares of capital
stock, and the date as of which it is expected that holders of record of shares
of capital stock or other securities constituting a part of the Warrant Stock
(or securities into which the Warrant Stock may be converted) shall be entitled
to exchange such shares or securities for securities or other property, if any,
deliverable upon such reclassification, recapitalization, reorganization,
consolidation, merger, share exchange, sale, lease, conveyance, transfer,
disposition, dissolution, liquidation or winding up.

          SECTION 13. Notices. All notices, consents, approvals, agreements and
other communications provided hereunder shall be in writing and delivered
personally, by mail, by overnight courier (providing proof of delivery) or by
telecopy and shall be sufficiently given to the Purchaser and the Company if
addressed or delivered to them at the following addresses:



                                      -13-

   15





          If to Company:            Administaff, Inc.
                                    19001 Crescent Springs Drive
                                    Kingswood, Texas 77339-3802
                                    Attention: General Counsel
                                    Telephone No.: (281) 348-3251
                                    Facsimile No.:  (281) 348-2859

          with a copy to:           Andrews & Kurth L.L.P.
                                    4200 Texas Commerce Tower
                                    Houston, Texas 77002
                                    Attention: G. Michael O'Leary
                                    Telephone No.: (713) 220-4360
                                    Facsimile No.:  (723) 220-4593

          If to the Purchaser:      American Express Company
                                    American Express Tower
                                    World Financial Center
                                    200 Vesey Street
                                    New York, New York 10285
                                    Attention:  General Counsel
                                    Telephone No.: (212) 640-5789
                                    Facsimile  No.:  (212) 267-9061

          with a copy to:           King & Spalding
                                    191 Peachtree Street
                                    Atlanta, Georgia 30303-1763
                                    Attention:  John J. Kelley III
                                    Telephone No.: (404) 572-3401
                                    Facsimile No.:  (404) 572-5146

or at such other address as any party may designate to any other party by
written notice. All such notices and communications shall be deemed to have been
duly given: (i) at the time delivered by hand, if personally delivered, (ii)
when received, if deposited in the mail, postage prepaid, (iii) when
transmission is verified, if telecopied, and (iv) on the next Business Day, if
timely delivered to an air courier guaranteeing overnight delivery.

          SECTION 14. Successors. Except as otherwise expressly provided herein
or in the Warrants, all covenants and agreements of this Agreement by or on
behalf of any of the parties hereto shall bind and inure to the benefit of the
respective successors and assigns, including those by operation of law, merger
or consolidation. In addition, except as otherwise expressly provided in the
Warrants, and whether or not any express assignment has been made, the
provisions of this Agreement which are for Purchaser's benefit as a purchaser or
Holder of a Warrant or Warrant Stock



                                      -14-

   16




are also for the benefit of, and enforceable by, any subsequent Holder of such a
Warrant or Warrant Stock.

          SECTION 15. Governing Law. This Agreement, the Warrants and the
Warrant Stock shall be governed by those provisions of the General Corporation
Law of the State of Delaware and Article 8 of the Delaware Uniform Commercial
Code which are necessarily applicable to securities issued by a Delaware
corporation and otherwise shall be deemed to be a contract made under the laws
of the State of New York and for all purposes shall be construed in accordance
with the internal laws of said state.

          SECTION 16. Benefits of this Agreement. Nothing in this Agreement
shall be construed to give to any Person other than the Company and the Holders
any legal or equitable right, remedy or claim under this Agreement; this
Agreement shall be for the sole and exclusive benefit of the Company and the
Holders.

          SECTION 17. Counterparts. This Agreement may be executed in any number
of counterparts and each such counterpart shall for all purposes be deemed to be
an original, and all such counterparts shall together constitute one and the
same instrument.

          SECTION 18. Amendment; Waivers. Except as otherwise expressly provided
herein, the provisions of this Agreement may be amended or waived and the
Company may take any action herein prohibited, or fail to take any action herein
required to be performed by it if, but only if, the Company has obtained the
written consent of the Holders of a majority of the Warrants in existence at the
time such amendment or waiver becomes effective. No failure or delay by any
party in exercising any right or remedy hereunder shall operate as a waiver
thereof, nor shall a waiver of a particular right or remedy on one occasion be
deemed a waiver of any other right or remedy or a waiver of the same right or
remedy on any subsequent occasion.

          SECTION 19. Jurisdiction. Each of the parties hereto hereby agrees
that any legal action or proceeding against such party with respect to this
Agreement, the Warrants or the Warrant Stock may be brought in the courts of the
State of New York or of the United States of America for the Southern District
of New York as the other party may elect, and, by execution and delivery hereof,
such party accepts and consents for itself and in respect of its property,
generally and unconditionally, the jurisdiction of the aforesaid courts and
agrees that such jurisdiction shall be exclusive, unless waived by the other
party in writing, with respect to any action or proceeding brought by such party
against the other party. Each of the parties hereto irrevocably consents to the
service of process out of any of the aforementioned courts in any such action or
proceeding by the mailing of the copies thereof by certified mail, return
receipt requested, postage prepaid, to it at its address set forth herein, such
service to become effective upon the earlier of (i) the date ten calendar days
after such mailing and (ii) any earlier date permitted by applicable law.





                                      -15-

   17




          SECTION 20. Specific Performance. The Company and the Holders
recognize that the rights of the Holder(s) and the Company under this Agreement
are unique and, accordingly, the Holder(s) and the Company shall, in addition to
such other remedies as may be available to any of them at law or in equity, have
the right to enforce their rights hereunder and thereunder by actions for
injunctive relief and specific performance to the extent permitted by law. The
Company and the Holders agree that monetary damages would not be adequate
compensation for any loss incurred by reason of a breach by them of the
provisions of this Agreement and the Company and each of the Holders hereby
agrees to waive in any action for specific performance the defense that a remedy
at law would be adequate. This Agreement is not intended to limit or abridge any
rights of the Holder(s) or the Company which may exist apart from this
Agreement.

          SECTION 21. Entire Agreement. The parties hereto agree that this
Agreement, the Purchase Agreement, the Confidentiality Agreement and the other
Transaction Documents constitute the entire agreement among the parties with
respect to the subject matter hereof and supersede all prior agreements and
understandings between them as to such subject matter; and there are no
restrictions, agreements, arrangements, oral or written, between any or all of
the parties relating to the subject matter hereof which are not fully expressed
or referred to herein or therein.

          SECTION 22. Severability. If any provision of this Agreement shall be
held or deemed to be, or shall in fact be, invalid, inoperative or unenforceable
as applied to any particular case in any jurisdiction or jurisdictions, or in
all jurisdictions or in all cases, because of the conflict of any provision with
any constitution, statute, rule or public policy, or for any other reason, such
circumstances shall not have the effect of rendering the provision or provisions
in question, invalid, inoperative or unenforceable in any other jurisdiction or
in any other case or circumstance or of rendering any other provision or
provisions herein contained invalid, inoperative or unenforceable to the extent
that such other provisions are not themselves actually in conflict with such
constitution, statute, rule or public policy, but this Agreement shall be
reformed and construed in any such jurisdiction or case as if such invalid,
inoperative or unenforceable provision had never been contained herein and such
provision reformed so that it would be valid, operative and enforceable to the
maximum extent permitted in such jurisdiction or in such case.



                                      -16-

   18


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


                                         ADMINISTAFF, INC.


                                         By:    /s/  PAUL J. SARVADI
                                              ---------------------------------
                                              Name:  Paul J. Sarvadi
                                              Title: President



                                         AMERICAN EXPRESS TRAVEL RELATED
                                            SERVICES COMPANY, INC.


                                         By:    /s/  ANNE BUSQUET
                                              ---------------------------------
                                              Name:  Anne Busquet
                                              Title: President, AERS