Exhibit 5.1

June 7, 2017

The Board Of Directors Of

Cross Country Healthcare, Inc.

5201 Congress Avenue, Suite 100B

Boca Raton, Florida 33487

Ladies and Gentlemen:

We are acting as counsel to Cross Country Healthcare, Inc., a Delaware corporation (the “Company”), in connection with the filing of a Registration Statement on Form S-8 with exhibits thereto (the “Registration Statement”) by the Company under the Securities Act of 1933, as amended (the “Act”), and the rules and regulations thereunder, relating to the registration of 2,000,000 shares of common stock, par value $0.0001 per share, of the Company (the “Shares”) reserved for issuance pursuant to awards under the Cross Country Healthcare, Inc. 2014 Omnibus Incentive Plan (f/k/a 2007 Stock Incentive Plan) (the “Plan”).

In so acting, we have participated in the preparation of the Registration Statement and have reviewed the corporate proceedings in connection with the Plan. We have also examined and relied upon originals or copies, certified or otherwise authenticated to our satisfaction, of all such corporate records, documents, agreements and instruments relating to the Company, and certificates of public officials and of representatives of the Company, and have made such investigations of law, and have discussed with representatives of the Company and such other persons such questions of fact, as we have deemed proper and necessary as a basis for rendering this opinion.

Based upon, and subject to, the foregoing, we are of the opinion that the Shares, when and to the extent issued pursuant to the provision of the Plan (including payment of the option exercise prices provided for therein), will be, assuming no change in the applicable law or pertinent facts, validly issued, fully paid and non-assessable.

We hereby consent to the filing of this opinion as Exhibit 5.1 to the Registration Statement. In giving the foregoing consent, we do not admit that we are in the category of persons whose consent is required under Section 7 of the Act or the rules and regulations of the Securities and Exchange Commission promulgated thereunder.

Very truly yours,

/s/ Proskauer Rose LLP