Exhibit 5.1

September 19, 2012

Natural Resource Partners L.P.

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, pursuant to Rule 415 under the Securities Act, of

1. 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 (the “Primary Common Units”); and

2. Up to 16,646,072 common units representing limited partner interests in the Partnership to be offered on a secondary basis by the selling unitholder named in the Registration Statement (the “Selling Common Units”).

The Primary Common Units and the Selling 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”).

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 Partnership 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.

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

Based upon and subject to the assumptions, qualifications, limitations and exceptions set forth herein, we are of the opinion that:

1. When (a) the Partnership has taken all necessary action to duly authorize and approve the issuance of such Primary Common Units, the terms of the offering thereof and related matters and (b) the Primary Common Units have been issued and delivered in accordance with the terms of the applicable definitive purchase, underwriting or similar agreement approved by the Partnership upon payment of the consideration thereof or provided for therein, then the Primary Common Units will be validly issued, fully paid and nonassessable; and

2. The Selling Common Units have been duly authorized, validly issued, fully paid and nonassessable.

The opinions expressed herein are qualified in the following respects:

A. 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.

B. 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 and the Constitution of the State of Delaware, as interpreted by the courts of the State of Delaware.

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.