Exhibit 5.1

DEWEY & LEBOEUF Dewey & LeBoeuf LLP 1301 Avenue of the Americas New York, NY 10019-6092   T +1 212 259-8000 F +1 212 259-6333

March 19, 2012

National Fuel Gas Company

6363 Main Street

Williamsville, New York 14221

Ladies and Gentlemen:

This opinion relates to the Registration Statement (“Registration Statement”) on Form S-3 to be filed on or about the date hereof with the Securities and Exchange Commission (“SEC”) by National Fuel Gas Company, a New Jersey corporation (“Company”), under the Securities Act of 1933, as amended (“1933 Act”), for the registration of the sale by the Company from time to time of (i) debt securities (“Debt Securities”), (ii) shares of the Company’s common stock, $1.00 par value (“Stock”), together with the common stock purchase rights appurtenant thereto (“Rights,” and together with the Stock, the “Shares”), (iii) contracts to purchase the Shares or other agreements or instruments requiring the Company to sell the Shares (collectively, “Stock Purchase Contracts”), and (iv) units, each representing ownership of a Stock Purchase Contract and either Debt Securities or U.S. Treasury securities (“Stock Purchase Units”). In connection therewith, we have reviewed such documents and records as we have deemed necessary to enable us to express an opinion on the matters covered hereby.

Based on the foregoing, we are of the opinion that:

1. All requisite action necessary to make any Debt Securities valid, legal and binding obligations of the Company shall have been taken when:

A. The Board of Directors of the Company (“Company Board”), or a duly appointed and authorized committee (“Authorized Board Committee”) thereof, shall have taken appropriate action (i) to authorize and approve the issuance and sale of the Debt Securities (including the terms and provisions thereof), the consideration to be received therefore and related matters, (ii) to authorize and approve the form and substance of the documents to be used in connection with the sale of the Debt Securities

Dewey & LeBoeuf LLP is a New York limited liability partnership.

NEW YORK | LONDON | WASHINGTON, DC | ABU DHABI | ALBANY | ALMATY | BEIJING | BOSTON | BRUSSELS

CHICAGO | DOHA | DUBAI | FRANKFURT | HONG KONG | HOUSTON | JOHANNESBURG (PTY ) LTD. | LOS ANGELES MADRID | MILAN | MOSCOW | PARIS | RIYADH AFFILIATED OFFICE | ROME | SAN FRANCISCO | SILICON VALLEY | WARSAW

National Fuel Gas Company

March 19, 2012

Page 2

(the “Debt Securities Sale Documents”) and (iii) to take or, subject to specified guidelines, to delegate to appropriate officers or representatives of the Company the authority to take and, pursuant thereto, such officers or representatives shall have taken, all other necessary final action to consummate the authorization of the issuance and sale of the Debt Securities;

B. The terms of issuance and sale of the Debt Securities and of their issuance and sale pursuant to the Debt Securities Sale Documents shall have been duly established in conformity with the terms as established by the Company Board or an Authorized Board Committee, shall not violate any applicable law, the organizational documents of the Company or result in a default under or breach of any agreement or instrument binding upon the Company and shall comply with any requirement or restriction imposed by any court or governmental body having jurisdiction over the Company;

C. The Debt Securities shall have been issued and delivered in accordance with the terms and provisions of the Indenture, dated as of October 1, 1999, between the Company and The Bank of New York Mellon, as Trustee; and

D. The Debt Securities shall have been duly executed and authenticated, and issued and sold for the consideration prescribed by, and otherwise in accordance with, their respective terms and as contemplated by the Registration Statement.

E. The Stock (to the extent such shares of Stock are to be issued upon the conversion, exchange or exercise of any Stock Purchase Contracts or Stock Purchase Units, registered on the Registration Statement, when such shares have been duly issued and delivered as contemplated by the terms of the Stock Purchase Contracts or Stock Purchase Units, respectively), when issued and sold in accordance with the applicable underwriting agreement with respect to the Stock or any other duly authorized, executed and delivered, valid and binding purchase or agency agreement for consideration that shall be at least equal to the aggregate par value of such shares of Stock.

2. All requisite action necessary to make the Stock validly issued, fully paid and non-assessable will have been taken provided that:

A. The Company Board or an Authorized Board Committee shall have taken appropriate action (i) to authorize and approve the issuance and sale of the Stock (including the terms and provisions thereof), the consideration to be received therefore (which shall be at least equal to the aggregate par value of such shares of Stock) and related matters, (ii) to authorize and approve the form and substance of the documents to be used in connection with the

National Fuel Gas Company

March 19, 2012

Page 3

issuance and sale of such Stock (the “Stock Sale Documents”), and (iii) to take or, subject to specified guidelines, to delegate to appropriate officers or representatives of the Company the authority to take and, pursuant thereto, such officers or representatives shall have taken, all other final action necessary to consummate the authorization of the issuance and sale of such Stock;

B. The terms of the issuance and sale of the Stock and of their issuance and sale pursuant to the Stock Sale Documents shall have been duly established in conformity with the terms as established by the Company Board or an Authorized Board Committee, shall not violate any applicable law, the organizational documents of the Company or result in a default under or breach of any agreement or instrument binding upon the Company and shall comply with any requirement or restriction imposed by any court or governmental body having jurisdiction over the Company;

C. The Stock Sale Documents shall have been duly executed and delivered by or on behalf of the parties thereto and shall have become effective as therein provided; and

D. The Stock shall have been issued and sold for the consideration contemplated by the Registration Statement.

3. The Rights, when issued as contemplated by the Registration Statement and in accordance with the terms and conditions of the Amended and Restated Rights Agreement, dated as of December 4, 2008, between the Company and The Bank of New York, will be validly issued.

4. With respect to any Stock Purchase Contracts and Stock Purchase Units to be offered by the Company pursuant to the Registration Statement (the “Stock Purchase Contracts and Stock Purchase Units”), all requisite action necessary to make any Stock Purchase Contracts and Stock Purchase Units valid, legal and binding obligations of the Company shall have been taken provided that:

A. The Company Board or an Authorized Board Committee shall have taken appropriate action (i) to authorize and approve the issuance and sale of the Stock Purchase Contracts and Stock Purchase Units (including the terms and provisions thereof), the consideration to be received therefore and for the underlying Stock or preferred stock, as applicable (which shall be at least equal to the aggregate par value of such shares of Stock or preferred stock, as applicable), and related matters, (ii) to authorize and approve the form and substance of the Stock Purchase Contracts and Stock Purchase Units and the documents evidencing and used in connection with the issuance and sale of the Stock Purchase Contracts and Stock Purchase Units (the “Stock Purchase Sale Documents”), and (iii) to take or, subject to specified guidelines, to delegate to appropriate officers or

National Fuel Gas Company

March 19, 2012

Page 4

representatives of the Company the authority to take and, pursuant thereto, such officers or representatives shall have taken, all other final action necessary to consummate the authorization of the issuance and sale of such Stock Purchase Contracts or Stock Purchase Units;

B. The terms of the Stock Purchase Contracts and Stock Purchase Units and of their issuance and sale pursuant to the Stock Purchase Sale Documents shall have been duly established in conformity with the terms as established by the Company Board or an Authorized Board Committee, shall not violate any applicable law, the organizational documents of the Company or result in a default under or breach of any agreement or instrument binding upon the Company and shall comply with any requirement or restriction imposed by any court or governmental body having jurisdiction over the Company; and

C. The Stock Purchase Contracts and Stock Purchase Units and the Stock Purchase Sale Documents shall have been duly executed, authenticated, issued and delivered for the consideration prescribed by, and otherwise in accordance with, their respective terms and as contemplated by the Registration Statement.

The opinion set forth in paragraph 3 herein is subject to the same limitations and qualifications contained in the opinion of Lowenstein Sandler PC referred to below.

This opinion is subject to (i) bankruptcy, insolvency, reorganization, moratorium, fraudulent transfer or any comparable provision of state law and other laws of general application affecting the rights and remedies of creditors and (ii) general principles of equity.

The opinions expressed herein are limited to the law of the State of New York and the federal law of the United States and, in the manner specified in the following sentences, the law of the State of New Jersey. We do not hold ourselves out as experts on the laws of the State of New Jersey. To the extent that such opinions relate to or are dependent upon matters governed by New Jersey law, we have relied upon an opinion of even date herewith of Lowenstein Sandler PC, special New Jersey counsel for the Company, which is being filed as an exhibit to the Registration Statement. As to all matters of New York law, Lowenstein Sandler PC is hereby authorized to rely upon this opinion to the same extent as if this opinion had been addressed to them.

National Fuel Gas Company

March 19, 2012

Page 5

We hereby consent to the use of this opinion as an exhibit to the Registration Statement and to the use of our name, as counsel, therein. In giving the foregoing consent, we do not thereby admit that we belong to the category of persons whose consent is required under Section 7 of the 1933 Act, or the rules and regulations promulgated thereunder.

Very truly yours,

/s/ Dewey & LeBoeuf LLP