Exhibit 5.1

November 12, 2013

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”), in connection with the registration by the Partnership with the Securities and Exchange Commission (the “Commission”) under the Securities Act of 1933 (the “Securities Act”) or the proposed offering and sale by the Partnership of common units representing limited partner interests in the Partnership consisting of Common Units having an aggregate offering price of up to $75,000,000 (the “Units”) to be issued and sold by the Partnership, pursuant to an equity distribution agreement dated November 12, 2013 (the “Equity Distribution Agreement”) between the Partnership, GP Natural Resource Partners LLC and NRP (GP) LP and Citigroup Global Markets Inc., BB&T Capital Markets, a division of BB&T Securities, LLC, UBS Securities, LLC and Wells Fargo Securities, LLC. Capitalized terms used but not defined herein shall have the meanings given such terms in the Equity Distribution Agreement.

The Common Units are being offered and sold pursuant to a prospectus supplement, dated November 12, 2013, (the “Prospectus Supplement”) filed with the Commission pursuant to Rule 424(b) on November 12, 2013, to the prospectus dated September 11, 2012 (such prospectus, as amended and supplemented by the Prospectus Supplement, the “Prospectus”), included in the Registration Statement on Form S-3 (Registration No. 333-183314) (the “Registration Statement”).

We have examined originals or copies, certified or otherwise identified to our satisfaction, of (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 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”); and (iv) 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) all information contained in all documents reviewed by us is true, (ii) all signatures on all documents examined by us are genuine, (iii) all documents submitted to us as originals are originals and all documents submitted to us as copies conform to the originals of those documents, (iv) the Registration Statement, and any amendments thereto (including post-effective amendments), will have become effective and (v) all Units will be sold in the manner stated in the Prospectus and the Equity Distribution Agreement.

Based on the foregoing, and subject to the assumptions, limitations and qualifications set forth herein, we are of the opinion that the Units are duly and validly authorized for issuance and, upon payment and delivery of the Units in accordance with the Equity Distribution Agreement, the Prospectus Supplement and the Prospectus, will be validly issued, fully paid (to the extent required by the Partnership Agreement) and non-assessable, except as such non-assessability may be affected by Sections 17-303, 17-607 and 17-804 of the Delaware Revised Uniform Limited Partnership Act and as described in the Prospectus.

The opinions expressed herein are limited exclusively to the Delaware Revised Uniform Limited Partnership Act and we are expressing no opinion as to the effect of the laws of any other jurisdiction.

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 and the Prospectus. In 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.