Exhibit 5.1

January 31, 2022

Natural Resource Partners L.P.

1201 Louisiana Street, Suite 3400

Houston, Texas 77002

Re:    Natural Resource Partners L.P. – Registration Statement on Form S-3

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”) under the Securities Act of 1933, as amended (the “Securities Act”), on the date hereof and to which this opinion is an exhibit. The Registration Statement relates to the offering for resale, from time to time, of up to 7,500,000 common units representing limited partner interests in the Partnership (the “Common Units”) to be offered on a secondary basis by the selling unitholders named in the Registration Statement. The Common Units are issuable upon conversion of preferred units representing limited partner interests in the Partnership (the “Preferred Units”). The Preferred Units were issued by the Partnership to the selling unitholders in a private placement pursuant to a Class A Convertible Preferred Unit and Warrant Purchase Agreement dated February 22, 2017. We have also participated in the preparation of the prospectus relating to the Registration Statement and included as a part thereof (the “Prospectus”).

In rendering the opinion set forth below, we have examined and relied upon (i) the Registration Statement, including the Prospectus; (ii) 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 (the “Delaware Act”) in connection with the formation of the Partnership; (iii) the Fifth Amended and Restated Agreement of Limited Partnership of the Partnership, dated as of March 2, 2017 (the “Partnership Agreement”); 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 (i) the legal capacity of all natural persons, the genuineness of all signatures, the authenticity of all documents submitted to us as originals, the conformity to original documents of all documents submitted to us as certified, conformed or photostatic copies and the authenticity of the originals of such latter documents, (ii) the parties to any

Vinson & Elkins LLP Attorneys at Law Austin Dallas Dubai Houston London Los Angeles New York Richmond Riyadh San Francisco Tokyo Washington 1001 Fannin Street, Suite 2500 Houston, TX 77002-6760 Tel +1.713.758.2222 Fax +1.713.758.2346 www.velaw.com

January 31, 2022 Page 2

executed documents, other than the Partnership, had the power, corporate or otherwise, to execute and deliver such documents, and the validity and binding effect thereof on such parties; (iii) all information contained in all documents reviewed by us is true and correct; (iv) the Registration Statement, and any amendments thereto (including post-effective amendments), will have become effective and comply with all applicable laws, (v) all Common Units will be issued and sold in compliance with applicable federal and state securities laws and in the manner specified in the Registration Statement and any applicable supplement to the Prospectus and (vi) if applicable, one or more supplements to the Prospectus contained in the Registration Statement will have been prepared and filed with the Commission describing the Common Units offered thereby.

Based upon and subject to the assumptions, qualifications, limitations and exceptions set forth herein, we are of the opinion that the Common Units have been duly authorized and will, when issued upon conversion of the Preferred Units in accordance with the terms of the Preferred Units, be validly issued and fully paid (to the extent required under the Partnership Agreement) and non-assessable (except as such non-assessability be affected by matters described in Sections 17-303, 17-607 and 17-804 of the Delaware Act and as described in any supplement to the Prospectus and the Prospectus).

The foregoing opinion is limited in all respects to the Delaware Act and the federal laws of the United States, 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 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.