Exhibit 99.4

LETTER TO NOMINEES

TEAMSTAFF, INC.

Up to            Shares of Common Stock
Issuable upon the Exercise of Non-transferrable Subscription Rights at $            per Share.

                    , 2012

To Security Dealers, Commercial Banks,
Trust Companies and Other Nominees:

        This letter is being sent by Teamstaff, Inc. (the "Company") to nominee holders of our common stock at 5:00 p.m., Eastern time, on                    , 2012 (the "Record Date") in connection with our distribution at no charge of (a) nontransferable rights ("Rights") to purchase shares of our common stock in a Rights offering by the Company (the "Rights Offering"). The Rights Offering are described in the enclosed offering prospectus dated                    , 2012 ("Prospectus").

        We are asking you as nominee for your clients who beneficially hold our common stock to contact the beneficial owners for instructions regarding the Rights Offering.

        Enclosed are copies of the following documents:

1.

Prospectus;



2.

A form of letter that may be sent to your clients for whose accounts you hold our common stock registered in your name or the name of your nominee;



3.

Beneficial Owner Election Form;



4.

Nominee Holder Certification;



5.

Notice of Guaranteed Delivery; and



6.

Notice of Tax Information.

        In the Rights Offering, we are offering up to            shares of common stock, as described in the Prospectus, at a price of $      per share. You will receive 1 Right for each            shares of common stock owned or held by you as nominee as of the Record Date, and each Right entitles you to purchase      share of common stock under what we refer to as your "Basic Subscription Right." In addition, if you exercise your Basic Subscription Right in full, you will be eligible, under what we refer to as your "Over-Subscription Privilege", to purchase any shares of common stock that are not purchased by other Rights holders under their Basic Subscription Rights. Exercise of your Over-Subscription Privilege is subject to limitation and allocation as further described in the Prospectus. Please note that fractional Rights will be rounded up to the nearest whole number of Rights. The Rights are not transferable and may not be sold.

        The Rights Offering will expire at 5:00 p.m., Eastern time, on                , 2012. Your right to purchase common stock in the Rights Offering will expire if not exercised by such time. Once submitted, all exercises of the Rights are irrevocable. You should read the Prospectus carefully before deciding whether to exercise your Rights.

        To exercise your Rights, you should deliver the properly completed and duly signed Beneficial Owner Election Form and the Nominee Holder Certification, with full payment of the subscription price for each share of common stock subscribed for pursuant to the Basic Subscription Right and the Over-Subscription Privilege, to the subscription agent, as indicated in the Prospectus.

1

        The subscription agent must receive the Beneficial Owner Election Form, the Nominee Holder Certification and all other required subscription documents with payment, including final clearance of any checks, prior to the expiration of the Rights Offering.

        Your prompt action is requested with respect to the Rights Offering.

        Please contact Continental Stock Transfer & Trust Company, who is the subscription agent for the Rights Offering additional copies of the enclosed materials and any questions or requests for assistance concerning either the Rights Offering.

Very truly yours,

TEAMSTAFF, INC.

John Khan,
Chief Financial Officer

        NOTHING IN THE PROSPECTUS OR IN THE ENCLOSED DOCUMENTS SHALL CONSTITUTE YOU OR ANY PERSON AS AN AGENT OF TEAMSTAFF, INC., THE SUBSCRIPTION OR ANY OTHER PERSON MAKING OR DEEMED TO BE MAKING OFFERS OF THE SECURITIES ISSUABLE UPON VALID EXERCISE OF THE RIGHTS, OR AUTHORIZE YOU OR ANY OTHER PERSON TO MAKE ANY STATEMENTS ON BEHALF OF ANY OF THEM WITH RESPECT TO THE RIGHTS OFFERING EXCEPT FOR 'STATEMENTS MADE IN THE PROSPECTUS.

2

QuickLinks

Exhibit 99.4