Exhibit 23.1

CONSENT OF REGISTERED INDEPENDENT PUBLIC ACCOUNTING FIRM

We hereby consent to the incorporation by reference of our report dated February 14, 2011 relating to the consolidated financial statements of TeamStaff, Inc. (the “Company”) as of and for the years ended September 30, 2010 and 2009 included in this Annual Report on Form 10-K into the Company’s previously filed Registration Statements on Form(s) S-3 (File Nos. 333-74478 and 333-120423) and Form(s) S-8 (File Nos. 333-73426 and 333-143951).

/s/ WithumSmith+Brown, PC WithumSmith+Brown, PC

Morristown, New Jersey

February 14, 2011