Exhibit 5.1

[Letterhead of O’Melveny & Myers LLP]

June 20, 2013

Progenics Pharmaceuticals, Inc.

777 Old Saw Mill River Road

Tarrytown, New York

Re: Issuance of Shares of Common Stock under Registration Statement on Form S-3 (File No. 333-176244)

Ladies and Gentlemen:

We have acted as special counsel to Progenics Pharmaceuticals, Inc., a Delaware corporation (the “Company”), in connection with the issuance and sale of (i) 8,500,000 shares (the “Firm Shares”) of common stock, par value $0.0013 per share, of the Company (“Common Stock”), and (ii) up to 1,275,000 shares of Common Stock (the “Optional Shares” and together with the Firm Shares, the “Offered Shares”) that may be sold by the Company pursuant to the exercise of an overallotment option granted to the Underwriters (as defined below), pursuant to an effective registration statement on Form S-3 (File No. 333-176244) (the “Registration Statement”) filed with the Securities and Exchange Commission (the “Commission”) under the Securities Act of 1933, as amended (the “Securities Act”), on August 11, 2011, as amended on September 8, 2011 and September 16, 2011, and declared effective by the Commission on September 19, 2011, the related prospectus that forms a part of the Registration Statement (the “Base Prospectus”), as supplemented by the prospectus supplement dated as of June 20, 2013 (the “Prospectus Supplement” and collectively with the Base Prospectus, the “Prospectus”), and that certain Underwriting Agreement dated as of June 20, 2013, by and between the Company and Jefferies LLC, as representative of the underwriters named therein (the “Underwriters”).

This opinion is being furnished in accordance with the requirements of Item 601(b)(5) of Regulation S-K under the Securities Act, and no opinion is expressed herein as to any matter pertaining to the contents of the Registration Statement or the Prospectus, other than as expressly stated herein with respect to the issuance of the Offered Shares.

In our capacity as such counsel, we have examined originals or copies of those corporate and other records, documents and agreements we considered appropriate. As to relevant factual matters, we have relied upon, among other things, factual representations we have received from the Company. In addition, we have obtained and relied upon those certificates of public officials we considered appropriate.

We have assumed the genuineness of all signatures, the authenticity of all documents submitted to us as originals and the conformity with originals of all documents submitted to us as copies.

On the basis of such examination, our reliance upon the assumptions in this opinion and our consideration of those questions of law we considered relevant, and subject to the limitations and qualifications in this opinion, we are of the opinion that the Offered Shares, when issued and sold in accordance with the Registration Statement and the Prospectus, will by validly issued, fully paid and non-assessable.

The law covered by this opinion is limited to the present Delaware General Corporation Law and the present federal law of the United States. We express no opinion as to the laws of any other jurisdiction and no opinion regarding the statutes, administrative decisions, rules, regulations or requirements of any county, municipality, subdivision or local authority of any jurisdiction.

We hereby consent to the use of this opinion as an exhibit to a Current Report on Form 8-K to be filed by the Company as of the date hereof and to the reference to this firm under the heading “Legal Matters” in the Prospectus Supplement. 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. This letter speaks only as of the date hereof and we assume no obligation to update or supplement this opinion to reflect any facts or circumstances that arise after the date of this opinion and come to our attention, or any future changes in laws.

Respectfully submitted,

/s/ O’Melveny & Myers LLP

2