Exhibit 5.1

Becker-Poliakoff, LLP

45 Broadway, 8th Floor

New York, New York 10006

Tel (212) 599-3322

April 30, 2012

Teamstaff, Inc.

1776 Peachtree St. NW

Suite 3005

Atlanta, GA 30309

Re:                             Rights Offering

Registration Statement on Form S-1

SEC Registration File 333-180152

Ladies and Gentlemen:

We have acted as counsel to Teamstaff, Inc., a New Jersey corporation (the “Company”), in connection with the Company’s Registration Statement on Form S-1 (SEC File No. 333-180152), as amended to the date hereof (the “Registration Statement”), filed with the Securities and Exchange Commission (the “Commission”) pursuant to the Securities Act of 1933, as amended (the “Securities Act”). The Registration Statement includes a prospectus (the “Prospectus”) to be furnished to shareholders of the Company as of the record date as stated therein in connection with the distribution by the Company to its stockholders of non-transferable subscription rights (the “Subscription Rights”) entitling the holders thereof to purchase up to an aggregate of 3,230,769 shares (the “Rights Shares”) of common stock, par value $0.001 per share (the “Common Stock”), of the Company (the “Rights Offering”). The Registration Statement relates to the issuance for no consideration of the Subscription Rights and the Rights Shares that may be issued and sold by the Company upon exercise of the Subscription Rights.

In arriving at the opinions expressed below, we have examined the originals, or photostatic or certified copies, of (i) the Registration Statement, as filed with the Commission under the Act on the date hereof; (ii) the Prospectus; (iii) the Articles of Incorporation of the Company, as amended to date; (iv) the By-laws of the Company, as amended to date and (iv) such other records of the Company and certificates of officers of the Company, of public officials and of such other documents as we have deemed relevant and necessary as the basis for the opinions set forth below. In our examination, we have assumed the genuineness of all signatures, the legal capacity and competency of all natural persons, the authenticity of all documents submitted to us as originals and the conformity to original documents of all documents submitted to us as copies.

The opinions set forth herein are subject to the following assumptions, qualifications, limitations and exceptions. We render no opinion herein as to matters involving the laws of any jurisdiction other than the New Jersey Business Corporation Act (which includes New Jersey statutory provisions and reported judicial decisions interpreting the New Jersey Business Corporation Act). The opinions set forth herein are made as of the date hereof, and we assume no obligation to supplement this opinion letter if any applicable laws change after the date hereof or if we become aware after the date hereof of any facts that might change the opinions express herein.

Based upon the foregoing examination and in reliance thereon, and subject to the assumptions stated and in reliance on statements of fact contained in the documents that we have examined, we are of the opinion that:

1.               the Subscription Rights have been duly authorized and, when issued, will be the valid and binding obligations of the Company, enforceable against the Company in accordance with their terms, except to the extent that enforcement thereof may be limited by applicable bankruptcy, insolvency, fraudulent conveyance, reorganization, moratorium, receivership or other laws relating to or affecting creditors’ rights generally, and to general principles of equity (regardless of whether enforcement is sought in a proceeding at law or in equity); and

2.               the Rights Shares have been duly authorized and, when issued and delivered against payment therefor upon due exercise of Subscription Rights as contemplated in the Prospectus, the Rights Shares will be validly

issued, and fully paid and non-assessable.

No opinion may be implied or inferred beyond the opinions expressly stated in the numbered paragraphs above. We have no obligation to update this opinion or to advise you after the date hereof of facts or circumstances that come to our attention or changes in law or any other matters that occur which could affect the opinions and other statements contained herein. This opinion may not be relied upon, furnished or quoted by you for any other purpose without our prior written consent.

We consent to the filing of this opinion as an exhibit to the Registration Statement, and we further consent to the use of our name under the caption “Legal Matters” in the Registration Statement and the prospectus that forms a part thereof. In giving these consents, we do not thereby admit that we are within the category of persons whose consent is required under Section 7 of the Securities Act or the Rules and Regulations of the Commission.  As stated in the prospectus contained in the Registration Statement, Mr. Victor DiGioia, a partner in the firm of Becker-Poliakoff LLP, holds 51,020 of our Common Stock and will be eligible to participate in the Rights Offering upon the same terms and conditions as other beneficial owners of our common stock.

This Opinion may be relied upon by Continental Stock Transfer & Trust Company as registrar and transfer agent to the Company and subscription agent with respect to the Rights Offering.