Exhibit 5.1

October 7, 2014

Natural Resource Partners L.P.

601 Jefferson Street, Suite 3600

Houston, Texas 77002

Ladies and Gentlemen:

We have acted as counsel for Natural Resource Partners L.P., a Delaware limited partnership (the “Partnership”), with respect to certain legal matters in connection with (i) the offer and sale by the Partnership of 8,500,000 common units representing limited partner interests in the Partnership (the “Offered Units”) pursuant to an Underwriting Agreement, dated as of October 6, 2014 (the “Underwriting Agreement”), among Citigroup Global Markets Inc. and Wells Fargo Securities, LLC, as representatives of the several underwriters (the “Underwriters”), the Partnership, NRP (GP) LP, a Delaware limited partnership (the “General Partner”) and GP Natural Resource Partners LLC, a Delaware limited liability company (the “Managing General Partner”), and (ii) the potential offering and sale of up to an additional 1,275,000 common units representing limited partner interests in the Partnership (the “Option Units” and, collectively with the Offered Units, the “Units”) pursuant to the exercise by the Underwriters of an option to purchase that number of additional units representing limited partner interests, which offering is being made pursuant to the Registration Statement on Form S-3 (Registration No. 333-180907) (as amended, the “Registration Statement”) and the Prospectus dated April 24, 2012 included therein (the “Base Prospectus”) by the Partnership under the Securities Act of 1933, as amended (the “Act”), with the Securities and Exchange Commission (the “SEC”). On October 7, 2014, the Partnership filed with the SEC the Base Prospectus and a prospectus supplement dated October 6, 2014 (the “Prospectus Supplement”) pursuant to Rule 424(b) promulgated under the Act.

In rendering the opinion set forth below, we have examined originals or copies, certified or otherwise identified to our satisfaction, of (i) the Registration Statement, including the Base Prospectus, (ii) the Prospectus Supplement, (iii) the Certificate of Limited Partnership, dated as of April 9, 2002, filed with the Secretary of State of Delaware pursuant to Delaware Revised Uniform Limited Partnership Act in connection with the formation of the Partnership; (iv) 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 (as amended, the “Partnership Agreement”), (iv) the Underwriting Agreement, (v) the resolutions of the board of directors and the equity pricing committee thereof and (vi) such other certificates, statutes and other instruments and documents as we consider appropriate for purposes of the opinions hereafter expressed.

In rendering the opinion set forth below, we have assumed that all Units will be issued and sold in compliance with applicable federal and state securities laws and in the manner stated in the Prospectus Supplement, the Base Prospectus and the Underwriting Agreement.

In connection with rendering the opinion set forth below, we have assumed that (i) all information contained in all documents reviewed by us is true and correct, (ii) all signatures on all documents examined by us are genuine, (iii) all documents submitted to us as originals are authentic and all documents submitted to us as copies conform to the originals of those documents and (iv) the Underwriting Agreement has been duly authorized, executed and delivered by the Underwriters and constitutes a legal, valid and binding obligation of the Underwriters, and that the Underwriters have the requisite organizational and legal power and authority to perform their obligations under the Underwriting Agreement.

Based upon the foregoing and subject to the assumptions, exceptions, limitations and qualifications set forth herein, we are of the opinion that when the Units have been issued and delivered in accordance with the terms of the Underwriting Agreement and upon payment of the consideration therefor provided for therein, the Units will be validly issued, fully paid (to the extent required under the Partnership Agreement) and nonassessable (except as such nonassessability may be affected by Sections 17-303, 17-607 and 17-804 of the Delaware Revised Uniform Limited Partnership Act (the “DRUPLA”)).

The opinion expressed herein is limited in all respects to the DRUPLA and the Delaware Limited Liability Company Act (including the applicable provisions of the Delaware Constitution and the reported judicial decisions interpreting these laws) and the federal laws of the United States of America, and we are expressing no opinion as to the effect of the laws of any other jurisdiction, domestic or foreign.

We hereby consent to the filing of this opinion of counsel as Exhibit 5.1 to the Current Report on Form 8-K of the Partnership dated on or about the date hereof, to the incorporation by reference of this opinion of counsel into the Registration Statement and to the reference to our Firm under the heading “Legal Matters” in the Prospectus Supplement. 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 of the SEC issued thereunder

Very truly yours,

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

Vinson & Elkins L.L.P.