Exhibit 5.1

April 14, 2012

Natural Resource Partners L.P.

NRP (Operating) LLC

601 Jefferson Street, Suite 3600

Houston, Texas 77002

Ladies and Gentlemen:

We have acted as counsel to Natural Resource Partners L.P., a Delaware limited partnership (the “Partnership”), with respect to certain legal matters in connection with the preparation of the Registration Statement on Form S-3 (the “Registration Statement”) filed with the Securities and Exchange Commission (the “Commission”) on the date hereof and to which this opinion is an exhibit. The Registration Statement relates to the offer and sale, from time to time, of up to $500,000,000 aggregate offering price of common units representing limited partner interests in the Partnership to be offered on a primary basis and the offering for resale, from time to time, of up to 16,646,072 common units representing limited partner interests in the Partnership to be offered on a secondary basis by the selling unitholders named in the Registration Statement.

The common units, are referred to herein as the “Securities.” We have also participated in the preparation of the prospectus relating to the Registration Statement and included as a part thereof (the “Prospectus”). The Securities may be offered in such amounts and at such prices and on such terms to be determined in light of market conditions at the time of offer and sale and to be set forth in a prospectus supplement to the Prospectus (a “Prospectus Supplement”).

In rendering the opinions set forth below, we have examined and relied upon (i) the Registration Statement, including the Prospectus; (ii) the Fourth Amended and Restated Agreement of Limited Partnership of the Partnership, dated as of September 20, 2010, as amended by the First Amendment thereto, dated as of March 6, 2012; (iii) the Amended and Restated Limited Liability Company Agreement of the NRP (Operating) LLC, dated as of October 17, 2002; (iv) the Fifth Amended and Restated Agreement of Limited Patnership of NRP(GP) LP, dated as of December 16, 2011, (v) the Fourth Amended and Restated Limited Liability Company Agreement of GP Natural Resource Partners LLC, dated as of January 4, 2007, and (vi) such certificates, statutes and other instruments and documents as we consider appropriate for purposes of the opinions hereafter expressed. In addition, we have reviewed such questions of law as we considered appropriate.

In connection with this opinion, we have assumed that (i) the Registration Statement, and any amendments thereto (including post-effective amendments), will have become effective and comply with applicable law; (ii) a Prospectus Supplement will have been prepared and filed with the Commission describing the Securities offered thereby; (iii) all Securities will be issued and sold in compliance with applicable federal and state securities laws and in the manner stated in

Vinson & Elkins LLP Attorneys at Law Austin Beijing Dallas Dubai Hong Kong Houston London Moscow New York Shanghai Tokyo Washington First City Tower, 1001 Fannin Street, Suite 2500 Houston, TX 77002-6760 Tel 713.758.2222 Fax 713.758.2346 www.velaw.com

Page 2

the Registration Statement and the applicable Prospectus Supplement; and (iv) a definitive underwriting or similar agreement with respect to any Securities offered will have been duly authorized and validly executed and delivered by the Partnership and/or the Operating Company or the selling unitholder(s) and the other parties thereto.

Based upon and subject to the assumptions, qualifications, limitations and exceptions set forth herein, we are of the opinion that: (i) the Partnership has taken all necessary action to approve the issuance of such Securities, the terms of the offering and related matters, (ii) any selling unitholder, if applicable, has taken all necessary action to approve the sale of the Securities, the terms of the offering and related matters, (iii) the applicable definitive underwriting or similar agreement has been duly authorized and validly executed and delivered by the parties thereto and (iv) the Securities have been issued and delivered in accordance with terms of the applicable definitive underwriting or similar agreement approved by the Partnership or any selling unitholder, if applicable, upon payment of the consideration therefore provided for therein, then the Securities will be validly issued, fully paid (to the extent required under the Partnership Agreement) and non-assessable (except as such non-assessability may be limited under Section 17-607 of the Delaware Revised Uniform Limited Partnership Act).

The opinions expressed herein are qualified in the following respects:

A. We have assumed, without independent verification, that the certificates for the Securities will conform to the specimens thereof examined by us and will have been duly countersigned by a transfer agent and duly registered by a registrar of the Securities.

B. We have assumed that (i) each document submitted to us for review is accurate and complete, each such document that is an original is authentic, each such document that is a copy conforms to an authentic original and all signatures on each such document are genuine, and (ii) each certificate from governmental officials reviewed by us is accurate, complete and authentic, and all official public records are accurate and complete.

C. We express no opinions concerning (i) the validity or enforceability of any provisions contained in the Indentures that purport to waive or not give effect to the rights to notices, defenses, subrogation or other rights or benefits that cannot be effectively waived under applicable law; or (ii) the enforceability of indemnification provisions to the extent they purport to relate to liabilities resulting from or based upon negligence or any violation of federal or state securities or blue sky laws.

D. This opinion is limited in all respects to federal law of the United States of America, the Delaware Revised Uniform Limited Partnership Act, the Delaware Limited Liability Company Act, the Constitution of the State of Delaware, as interpreted by the courts of the State of Delaware, and the laws of the State of New York.

We hereby consent to the references to this firm under the caption “Legal Matters” in the Prospectus and to the filing of this opinion as an exhibit to the Registration Statement. By giving such 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 of the Commission issued thereunder.

Very truly yours,

/s/ Vinson & Elkins L.L.P.