ONE SHELL PLAZA
910 LOUISIANA
HOUSTON, TEXAS
77002-4995

TEL +1 713.229.1234
FAX +1 713.229.1522
www.bakerbotts.com

AUSTIN
BEIJING
DALLAS
DUBAI
HONG KONG
HOUSTON
LONDON
MOSCOW
NEW YORK
RIYADH
WASHINGTON

May 29, 2008

Administaff, Inc.
19001 Crescent Springs Drive
Kingwood, Texas 77339-3802

Ladies and Gentlemen:

     As set forth in the Registration Statement on Form S-8 (the “Registration Statement”) to be filed by Administaff, Inc., a Delaware corporation (the “Company”), with the Securities and Exchange Commission (the “Commission”) under the Securities Act of 1933, as amended (the “Act”), relating to the issuance of 1,500,000 shares (the “Shares”) of common stock, par value $.01 per share, of the Company pursuant to the Company’s 2008 Employee Stock Purchase Plan (as amended, the “Plan”), certain legal matters with respect to the Shares are being passed upon for the Company by us. At your request, this opinion is being furnished to you for filing as Exhibit 5.1 to the Registration Statement.

     We have examined originals, or copies certified or otherwise identified, of the Certificate of Incorporation and Bylaws of the Company, each as amended to date, the Plan, corporate records of the Company, including minute books of the Company, as furnished to us by the Company, certificates of public officials and of representatives of the Company, statutes and other instruments and documents as a basis for the opinions hereinafter expressed. In giving such opinions, we have relied upon certificates of officers of the Company and of public officials with respect to the accuracy of the material factual matters contained in such certificates. In giving the opinions below, we have assumed that the signatures on all documents examined by us are genuine, that all documents submitted to us as originals are accurate and complete, that all documents submitted to us as copies are true and correct copies of the originals thereof and that all information submitted to us was accurate and complete. In addition, we have assumed for purposes of this opinion that the consideration received by the Company for the Shares will be not less than the par value of the Shares.

     On the basis of the foregoing, and subject to the assumptions, limitations and qualifications set forth herein, we are of the opinion that the Shares have been duly authorized and, when issued and delivered against payment of the purchase price thereof in accordance with the terms and provisions of the Plan, will be validly issued, fully paid and nonassessable.

     The opinions set forth above are limited in all respects to matters of the General Corporation Law of the State of Delaware.

     We hereby consent to the filing of this opinion with the Commission as Exhibit 5.1 to the Registration Statement. In giving such consent, we do not admit that we are in the

-2-

May 29, 2008

category of persons whose consent is required under Section 7 of the Act or the rules and regulations of the Commission.

Very truly yours,
 

/s/ Baker Botts L.L.P.  

KBR/RR