Exhibit 5.1

August 11, 2015

Denbury Resources Inc.

5320 Legacy Drive

Plano, Texas 75024

Re: Denbury Resources Inc. - Registration Statement on Form S-8

Ladies and Gentlemen:

We have acted as outside counsel to Denbury Resources Inc., a Delaware corporation (the “Company”), in connection with the preparation of the Registration Statement on Form S-8 (the “Registration Statement”) to be filed with the Securities and Exchange Commission on or about August 12, 2015, under the Securities Act of 1933, as amended (the “Securities Act”), relating to 3,000,000 additional shares of the $0.001 par value common stock (the “Common Stock”) of the Company that may be issued by the Company under the Denbury Resources Inc. Amended and Restated 2004 Omnibus Stock and Incentive Plan (the “2004 Plan”). For the purposes hereof, the 3,000,000 additional shares of Common Stock that may be issued under the 2004 Plan will be referred to collectively as the “Shares.”

You have requested an opinion with respect to certain legal aspects of the issuance of the Shares. In connection therewith, we have examined and relied upon the originals, or copies identified to our satisfaction, of (1) the Second Restated Certificate of Incorporation of the Company and the Second Amended and Restated Bylaws of the Company; (2) minutes and records of the corporate proceedings of the Company with respect to the amendment and restatement of the 2004 Plan, the issuance of the Shares pursuant to the 2004 Plan, the filing of the Registration Statement with the Securities and Exchange Commission and related matters; (3) the Registration Statement and exhibits thereto; (4) the 2004 Plan; and (5) such other documents and instruments as we have deemed necessary for the expression of the opinion herein contained.

In making the foregoing examinations, we have assumed the genuineness of all signatures and the authenticity of all documents submitted to us as originals, and the conformity to original documents of all documents submitted to us as certified or photostatic copies. As to various questions of fact material to this opinion, and as to the content of the Registration Statement, minutes, records, resolutions and other documents or writings of the Company, we have relied, to the extent deemed reasonably appropriate, upon representations or certificates of officers or directors of the Company and upon documents, records and instruments furnished to us by the Company, without independent verification of their accuracy.

Based upon our examinations, and the consideration of, and reliance upon, the documents and other matters described above, and assuming that:

(1)    the Shares to be issued or sold in the future under the 2004 Plan will be duly issued or sold in accordance with the terms of the 2004 Plan and the terms of awards made under the 2004 Plan,

(2)    the Company maintains an adequate number of authorized but unissued shares and/or treasury shares for issuance of Shares to be issued pursuant to awards granted under the 2004 Plan, and

(3)    the lawful consideration for the Shares issued pursuant to the awards granted under the 2004 Plan, is actually received by the Company as provided in the 2004 Plan and exceeds the par value of such Shares,

Denbury Resources Inc.

August 11, 2015

Page 2

we are of the opinion that Shares issued or sold in accordance with the terms of the 2004 Plan and pursuant to awards made under and in accordance with the terms of the 2004 Plan, will be legally issued, fully paid and nonassessable.

The opinion expressed herein is limited to the General Corporation Law of the State of Delaware, including the applicable provisions of the Delaware Constitution and reported judicial decisions, rules and regulations interpreting and implementing those laws, and we assume no responsibility as to the applicability thereto, or the effect thereon, of the laws of any other jurisdiction.

We hereby consent to the filing of this opinion as an exhibit to the Registration Statement and any amendments thereto. In giving this consent, we do not admit that we come within the category of persons whose consent is required under Section 7 of the Securities Act or the Rules and Regulations of the Securities and Exchange Commission thereunder.

Very truly yours,

/s/ Baker & Hostetler LLP

Baker & Hostetler LLP