Exhibit 99.1

FOR IMMEDIATE RELEASE

TEAMSTAFF REPORTS SECOND QUARTER RESULTS

·                  Quarterly revenues grow sequentially and over prior year by 10% and 21%, respectively

·                  Company  positioning for bidding larger new contracts

·                  Subsequent to quarter’s end, Company receives contract modifications related to retroactive billing adjustments and commenced a rights offering of $4.2 million

·                  Management to conduct conference call/webcast today, May 16, 2012 at 11:00 a.m. ET

Atlanta, Georgia — May 16, 2012 — TeamStaff, Inc. (NASDAQ: TSTF), a leading healthcare and logistics services provider to the Federal Government, including the Departments of Defense and Veterans Affairs, announced today financial results for its second quarter ended March 31, 2012.

Table 1 - Financial Highlights

Commenting on the Company’s results, TeamStaff’s President and Chief Executive Officer Zachary Parker stated, “While the second quarter results reflect significantly improved results on the top line due to the ramp up of our renewed and enhanced CMOPs contract that commenced during November 2011, we incurred losses due to increased direct labor expenses stemming in large part from workers’ compensation claims expense related to prior periods as well as the historical effect in this quarter of higher payroll taxes. These additional expenses lowered our gross profit margin in the quarter and adversely impacted our ability to achieve better operating results.”

The Company added to certain operational overhead in the quarter to prepare bids for several contracts that are in its  business development pipeline. In addition, by commencing its rights offering, the Company is taking steps to strengthen its capital structure to support growth. The Company also received, subsequent to quarter’s end, contract modifications which should facilitate the resolution of its retroactive billing adjustments.

Mr. Parker concluded, “We believe that we are positioned well for growth and that the new platform we have built for future opportunities is ready to attract additional business. In the interim, we continue to keep tight expense controls, and have begun to move forward to convert our business pipeline into actionable contracts. We are confident in our ability to receive additional government contracts thanks in part to our impeccable track record and we are excited about our prospects, which are of utmost importance in our long term goal of improving shareholder value.”

Three Month Results

Revenues from TeamStaff’s continuing operations for the three months ended March 31, 2012 and 2011 were $12.6 million and $10.4 million, respectively, which represented an increase of $2.2 million or 21.2% despite extended government delays in major awards. The increase in operating revenues is due primarily to new business awards.

Gross profit for the three months ended March 31, 2012 and 2011 was $1.3 million and $1.5 million, respectively, which represents a decrease of $0.2 million or 13.3% despite the revenue increase. Gross profit from continuing operations, as a percentage of revenue, was 10.3% and 14.4%, for the three months ended March 31, 2012 and 2011, respectively. The key drivers for the period over period decrease in gross profit (as a percentage of revenue) were increased workers’ compensation claims expense related to previously incurred but not yet reported claims from 2009 — 2011 of approximately $0.2 million and a reduction in the prior year direct expenses of approximately $0.2 million, related to obtaining an independent trustee consent to utilize surplus assets in a medical benefit plan.

General and administrative (G&A) expenses for the three months ended March 31, 2012 and 2011 were $1.8 million and $1.6 million, respectively, which represent an increase of $0.2 million, or 12.5%. The difference is related to new contract operational overhead as well as to expanded new business development activity.

Loss from operations for the three months ended March 31, 2012 was $0.6 million as compared to loss from operations for the three months ended March 31, 2011 of $0.1 million.   The increase is primarily due to greater workers’ compensation claims expense related to previously incurred but not yet reported claims, the non-reoccurrence of a prior year trustee consent, new contract costs and expanded new business development efforts.

Loss from continuing operations for the three months ended March 31, 2012 was $0.7 million, or ($0.12) per basic and diluted share, as compared to loss from continuing operations of $0.2 million, or ($0.04) per basic and diluted share for the three months ended March 31, 2011.

Earning (Loss) Before Interest Tax Depreciation and Amortization (“EBITDA”) adjusted for other non-cash charges (“Adjusted EBITDA”(1)) for the three months ended March 31, 2012 was ($487,000) as compared to ($27,000) for the three months ended March 31, 2011, which shows a decrease of $460,000, reflecting the lower gross margin and increased SG&A expense.

Six Month Results

Revenues from TeamStaff’s operations from the six months ended March 31, 2012 and 2011 were $24.1 million and $21.0 million respectively, which represented an increase of $3.1 million or 14.8% over the prior fiscal period.  The increase in revenues from continuing operations is due primarily to the impact of new business awards.

Gross profit for the six months ended March 31, 2012 and 2011 were $2.9 million and $2.8 million, respectively which represents an increase $0.1 million or 3.6% over the prior fiscal year period. Gross profit from continuing operations, as a percentage of revenue, was 11.9 and 13.4%, for the six months ended March 31, 2012 and 2011, respectively. The key driver for the period over period increase in gross profit was the impact of new business awards, although factors such as increased workers’ compensation claims expense related to previously incurred but not yet reported claims from 2009 — 2011 of approximately $0.4 million and a reduction in the prior year direct expenses of approximately $0.2 million, related to obtaining an independent trustee consent to utilize surplus assets in a medical benefit plan, resulted in a decline in gross profit as a percentage of revenue.

G&A expenses for the six months ended March 31, 2012 and 2011 were $3.6 million and $3.1 million, respectively, which represent an increase of $0.5 million, or 14.9%. The difference is attributed largely to costs and investments associated with start-up of work under new contracts in three different states during the year, issuance of non-cash stock grants, and expanded new business development activity.

Loss from operations for six months ended March 31, 2012 was $0.8 million as compared to loss from operations for the six months ended March 31, 2011 of $0.4 million. The increase is similarly due to greater workers’ compensation claims expense related to previously incurred but not yet reported claims, the non-reoccurrence of a prior year trustee consent, new contract start-up costs and expanded new business development efforts.

Loss from continuing operations for the six months ended March 31, 2012 was $1.1 million, or ($0.18) per basic and diluted share, as compared to loss from continuing operations of $0.5 million, or ($0.10) per basic and diluted share for the six months ended March 31, 2011.

Earnings (Loss) Before Interest Tax Depreciation and Amortization (“EBITDA”) adjusted for other non-cash charges (“Adjusted EBITDA”(1)) for the six months ended March 31, 2012 was ($503,000) as compared to ($204,000) for the six months ended March 31, 2011, which shows a decrease of $299,000, reflecting the lower gross margin percentage and increased SG&A expense.

(1)         We present Adjusted EBITDA as a supplemental non-GAAP measure of our performance. We define Adjusted EBITDA as net loss from continuing operations plus (i) interest and other expenses, net, (ii) provision for or benefit from income taxes, if any, (iii) depreciation and amortization, (iv) G&A expenses — equity grants, and (v) impairment charges. This non-GAAP measure of our performance is used by management to conduct and evaluate its business during its regular review of operating results for the periods presented. Management and the Company’s Board utilize this non-GAAP measure to make decisions about the use of the Company’s resources, analyze performance between periods, develop internal projections and measure management performance. We believe that this non-GAAP measure is useful to investors in evaluating the Company’s ongoing operating and financial results and understanding how such results compare with the Company’s historical performance. By providing this non-GAAP measure, as a supplement to GAAP information, we believe we are enhancing investors’ understanding of our business and our results of operations. This non-GAAP financial measure is limited in its usefulness and should be considered in addition to, and not in lieu of, US GAAP financial measures. Further, this non-GAAP measure may be unique to the Company, as it may be different from the definition of non-GAAP measures used by other companies. A reconciliation of Adjusted EBITDA with net loss from continuing operations is as follows:

Conference Call and Webcast Details

TeamStaff’s management team will host a conference call for the investment community on Wednesday, May 16, 2012 at 11:00 AM ET.  Interested parties may participate in the call by dialing (877) 556-5921; international callers dial (617) 597-5474 (passcode: 97392514) about 5 — 10 minutes prior to 11:00 AM EDT.  The conference call will also be available on replay starting at 1:00 PM ET on May 16, 2012 and ending on May 23, 2012. For the replay, please dial (888) 286-8010 (passcode: 92551923). The access number for the replay for international callers is (617) 801-6888 (passcode: 92551923).  There will be a conference call webcast at:

http://edge.media-server.com/m/p/jc7f7z82/lan/en .

About TeamStaff, Inc.

TeamStaff Inc. (Nasdaq: TSTF - News) serves clients throughout the United States as a full-service provider of healthcare, logistics, and technical support services to DoD and Federal agencies.  The company recently gained approval from shareholders to change TeamStaff, Inc.’s corporate name to DLH Holdings Corp., which the company intends to implement subsequent to the conclusion of the rights offering that it is currently conducting. For more information, visit the corporate web site at www.dlhcorp.com.

“Safe Harbor” Statement under the Private Securities Litigation Reform Act of 1995:

This press release may contain forward-looking statements. These statements relate to future events or TeamStaff’s future financial performance. Any statements that are not statements of historical fact (including without limitation statements to the effect that the Company or its management “believes”, “expects”, “anticipates”, “plans” (and similar expressions) should be considered forward looking statements. There are a number of important factors that could cause TeamStaff’s actual results to differ materially from those indicated by the forward looking statements. including those factors described under “Risk Factors” in the Company’s prospectus included as part of the Registration Statement on Form S-1 filed by the Company in connection with the Rights Offering and in its periodic reports filed with the Securities and Exchange Commission from time to time. Given these risks and uncertainties, you are cautioned not to place undue reliance on forward-looking statements.  TeamStaff undertakes no obligation to publicly update or revise any forward-looking statement as a result of new information, future events, changes in expectation or otherwise, except as required by law.

TEAMSTAFF, INC. AND SUBSIDIARIES

CONSOLIDATED BALANCE SHEETS

(AMOUNTS IN THOUSANDS)

The accompanying notes are an integral part of these consolidated financial statements.

TEAMSTAFF, INC. AND SUBSIDIARIES

CONSOLIDATED BALANCE SHEETS

(AMOUNTS IN THOUSANDS EXCEPT PAR VALUE OF SHARES)

The accompanying notes are an integral part of these consolidated financial statements.

TEAMSTAFF, INC. AND SUBSIDIARIES

CONSOLIDATED STATEMENTS OF OPERATIONS

(AMOUNTS IN THOUSANDS, EXCEPT PER SHARE AMOUNTS)

The accompanying notes are an integral part of these consolidated financial statements

TEAMSTAFF, INC. AND SUBSIDIARIES

CONSOLIDATED STATEMENTS OF OPERATIONS

(AMOUNTS IN THOUSANDS, EXCEPT PER SHARE AMOUNTS)

The accompanying notes are an integral part of these consolidated financial statements.

- More -

CONTACTS:

Zachary C. Parker, President and Chief Executive Officer

John E. Kahn, Chief Financial Officer

TeamStaff, Inc.

1776 Peachtree Street, NW

Atlanta, GA 30309

866-952-1647

Christy N. Buechler, Marketing & Communications Manager (Media)

TeamStaff, Inc.

404-985-8818

christy.buechler@teamstaff.com

(Investor Relations)

Donald C. Weinberger/Adam Lowensteiner

Wolfe Axelrod Weinberger Associates, LLC

212-370-4500

don@wolfeaxelrod.com

adam@wolfeaxelrod.com

###