Exhibit 5.1

Kramer Levin Naftalis & Frankel LLP

June 14, 2012

Conmed Healthcare Management, Inc.

7250 Parkway Drive, Suite 400

Hanover, Maryland 21076

Re: Conmed Healthcare Management, Inc. Registration Statement on Form S-8

Ladies and Gentlemen:

We have acted as counsel to Conmed Healthcare Management, Inc., a Delaware corporation (the “Company”), in connection with the preparation and filing of a Registration Statement on Form S-8 (the “Registration Statement”) with the Securities and Exchange Commission (the “SEC”) with respect to the registration under the Securities Act of 1933, as amended (the “Securities Act”), of 1,000,000 shares (the “Shares”) of the Company’s common stock, par value $0.0001 per share, which may be issued pursuant to the Company’s 2007 Stock Option Plan, as amended (as the same may be further amended from time to time, the “Plan”).

In rendering this opinion, we have examined copies of the following documents (collectively, the “Transaction Documents”):

A. the Registration Statement,

B. the Plan,

C. the Certificate of Incorporation and Second Amended and Restated By-laws of the Company, and

D. the resolutions of the Board of Directors of the Company relating to the approval of the Plan.

We have also reviewed such other documents and made such other investigations as we have deemed appropriate. As to various questions of fact material to this opinion, we have relied upon the representations and warranties of the Company contained in the Transaction Documents and upon the statements, representations and certificates of officers or representatives of the Company, public officials and others. We have not independently verified the facts so relied on.

Based on the foregoing, and subject to the qualifications, limitations and assumptions set forth herein, we are of the opinion that the Shares have been duly authorized and, upon the issuance thereof and payment therefor in accordance with the terms stated in the Plan or in the award agreements entered into pursuant thereto, will be validly issued, fully paid and non-assessable.

Kramer Levin Naftalis & Frankel LLP

Conmed Healthcare Management, Inc.

June 14, 2012

Page 2

The Plan does not contain a provision specifying the law under which it is governed.  We have rendered our opinion as if the Plan were governed by the laws of the State of New York (without regard to the principles of conflict of laws).

We express no opinion as to the laws of any jurisdiction other than the federal laws of the United States, the laws of the State of New York, and the General Corporation Law of the State of Delaware.

We hereby consent to the use of this opinion as an exhibit to the Registration Statement. In giving the foregoing consent, we do not thereby admit that we are in the category of persons whose consent is required under Section 7 of the Securities Act or the rules and regulations of the SEC thereunder.

Very truly yours,

/s/ Kramer Levin Naftalis & Frankel LLP