Exhibit 5.1

October 30, 2013

Board of Directors

MELA Sciences, Inc.

50 South Buckhout Street

Irvington, New York 10533

Ladies and Gentlemen:

We are acting as counsel to MELA Sciences, Inc., a Delaware corporation (the “Company”), in connection with its registration statement on Form S-3, as amended (file no. 333-189118) (the “Registration Statement”), filed with the Securities and Exchange Commission under the Securities Act of 1933, as amended (the “Act”) relating to the proposed public offering of: (i) up to 4,228,181 shares of common stock, par value $0.001 per share (“Common Stock”) of the Company (the “Shares”), all of which are to be sold by the Company pursuant to those Securities Purchase Agreements among the Company and the purchasers party thereto (together, the “Purchase Agreement”); (ii) common stock purchase warrants to purchase up to 6,857,142 shares of Common Stock evidenced by warrants in the form filed by the Company as Exhibit 4.1 to its Current Report on Form 8-K on October 30, 2013 (the “Series A Warrants”); (iii) pre-funded warrants to purchase up to 4,343,247 shares of Common Stock evidenced by warrants in the form filed by the Company as Exhibit 4.2 to its Current Report on Form 8-K on October 30, 2013 (the “Series B Warrants” and together with Series A Warrants, the “Warrants”), and (iv) up to 11,200,389 shares of Common Stock issuable upon exercise of the Warrants (the “Warrant Shares” and together with the Shares and the Warrants, the “Securities”), as set forth in the Prospectus, dated October 25, 2013, which forms a part of the Registration Statement, as supplemented by the Prospectus Supplement, dated October 30, 2013.

We have examined and reviewed only such documents, records and matters of law as we have deemed necessary or appropriate for the purpose of rendering the opinion set forth herein. Insofar as the opinion set forth herein is based on factual matters in connection with, among other things, the issuance of the Securities, which factual matters are authenticated in certificates from certain officers of the Company, we have relied on such certificates. We have assumed the genuineness of all signatures, the authenticity of all documents submitted to us as originals and the conformity to originals of all documents submitted to us as certified or reproduced copies.

Based upon, subject to and limited by the foregoing, we are of the opinion that:

(a) Following the issuance of the Shares pursuant to the terms of the Purchase Agreement, and receipt by the Company of the consideration for the Shares specified in the Purchase Agreement, the Shares will be validly issued, fully paid, and non-assessable.

(b) Following (i) execution and delivery by the Company of the Warrants pursuant to the terms of the Purchase Agreement, (ii) receipt by the Company of the consideration for the Warrants as specified for in the Purchase Agreement, (iii) exercise of the Warrants pursuant to terms thereof, (iv) receipt by the Company of the exercise price for the Warrant Shares as specified in the Warrants and (v) issuance of the Warrant Shares thereunder, the Warrant Shares will be validly issued, fully paid, and non-assessable.

We express no opinion as to the applicability or effect of any laws, orders or judgments of any state or other jurisdiction other than federal securities laws and the General Corporation Law of the State of Delaware. Further, this opinion speaks as of the date hereof and is based solely upon existing laws, rules and regulations, and we undertake no obligation to advise you of any changes that may be brought to our attention after the date hereof. This opinion is expressly limited to the matters set forth above and we render no opinion, whether by implication or otherwise, as to any other matters relating to the Company or the Securities.

This opinion is issued to you solely for use in connection with the Registration Statement and is not to be quoted or otherwise referred to in any financial statements of the Company or any other document, nor is it to be filed with or furnished to any government agency or other person, without our prior written consent.

We hereby consent to the use of our name under the caption “Legal Matters” in the prospectus supplement, dated October 30, 2013, relating to the Securities, and to the filing of this opinion as an exhibit to the Company’s Current Report on Form 8-K, filed on October 30, 2013. In giving this consent, we do not 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 adopted under the Securities Act.

Very truly yours,

/s/ Golenbock Eiseman Assor Bell & Peskoe LLP