Exhibit 4.1

AMENDMENT NO. 1

TO

FOURTH AMENDED AND RESTATED

AGREEMENT OF LIMITED PARTNERSHIP

OF

NATURAL RESOURCE PARTNERS L.P.

This Amendment No. 1 (this “Amendment No. 1”) to the Fourth Amended and Restated Agreement of Limited Partnership of Natural Resource Partners L.P. (the “Partnership”) is entered into effective as of March 6, 2012, by NRP (GP) LP, a Delaware limited partnership (the “General Partner”), as general partner of the Partnership. Capitalized terms used but not defined herein are used as defined in the Partnership Agreement.

WHEREAS, the General Partner entered into that certain Fourth Amended and Restated Agreement of Limited Partnership of the Partnership dated as of September 20, 2010 (the “Partnership Agreement”);

WHEREAS, Section 13.1(d)(i) of the Partnership Agreement provides that the General Partner may amend any provision of the Partnership Agreement without the approval of any Partner or Assignee to reflect a change that, in the discretion of the General Partner, does not adversely affect the Limited Partners (including any particular class of Partnership Interests as compared to other classes of Partnership Interests) in any material respect; and

WHEREAS, acting pursuant to the power and authority granted to the General Partner under Section 13.1(d)(i) of the Partnership Agreement, the General Partner has determined that the following amendment to the Partnership Agreement does not adversely affect the Limited Partners (including any particular class of Partnership Interests as compared to other classes of Partnership Interests) in any material respect.

NOW THEREFORE, the General Partner does hereby amend the Partnership Agreement as follows:

Section 1. Amendment.

(a) Section 7.12(a) is hereby amended and restated in its entirety as follows:

(a) If (i) the General Partner or any Affiliate of the General Partner, including Adena, (including for purposes of this Section 7.12, any Person that was an Affiliate of the General Partner at the Closing Date, notwithstanding that it may later cease to be an Affiliate of the General Partner or Adena) holds Partnership Securities that it desires to sell and (ii) Rule 144 of the Securities Act (or any successor rule or regulation to Rule 144) or another exemption from registration is not available to enable such holder of Partnership Securities (the “Holder”)

AMENDMENT NO. 1

TO

FOURTH AMENDED AND RESTATED AGREEMENT OF LIMITED PARTNERSHIP

OF NATURAL RESOURCE PARTNERS L.P.

to dispose of the number (without limitation) of Partnership Securities it desires to sell at the time it desires to do so without registration under the Securities Act, then at the option and upon the request of the Holder, the Partnership shall file with the Commission as promptly as practicable after receiving such request, and use all commercially reasonable efforts to cause to become effective and remain effective for a period of not less than six months following its effective date or such shorter period as shall terminate when all Partnership Securities covered by such registration statement have been sold, a registration statement under the Securities Act registering the offering and sale of the number of Partnership Securities specified by the Holder; provided, however, that after November 1, 2011, the Partnership shall not be required to effect more than three registrations pursuant to Section 7.12(a) and Section 7.12(b) at the request of Adena or more than one registration pursuant to Section 7.12(a) and Section 7.12(b) at the request of each of Western Pocahontas, Great Northern and New Gauley; and provided further, however, that if the Conflicts Committee determines that the requested registration would be materially detrimental to the Partnership and its Partners because such registration would (x) materially interfere with a significant acquisition, reorganization or other similar transaction involving the Partnership, (y) require premature disclosure of material information that the Partnership has a bona fide business purpose for preserving as confidential or (z) render the Partnership unable to comply with requirements under applicable securities laws, then the Partnership shall have the right to postpone such requested registration for a period of not more than three months after receipt of the Holder’s request, such right pursuant to this Section 7.12(a) or Section 7.12(b) not to be utilized more than twice in any twelve-month period. Except as provided in the preceding sentence, the Partnership shall be deemed not to have used all commercially reasonable efforts to keep the registration statement effective during the applicable period if it voluntarily takes any action that would result in Holders of Partnership Securities covered thereby not being able to offer and sell such Partnership Securities at any time during such period, unless such action is required by applicable law. In connection with any registration pursuant to the first sentence of this Section 7.12(a), the Partnership shall (i) promptly prepare and file (A) such documents as may be necessary to register or qualify the securities subject to such registration under the securities laws of such states as the Holder shall reasonably request; provided, however, that no such qualification shall be required in any jurisdiction where, as a result thereof, the Partnership would become subject to general service of process or to taxation or qualification to do business as a foreign corporation or partnership doing business in such jurisdiction solely as a result of such registration, and (B) such documents as may be necessary to apply for listing or to list the Partnership Securities subject to such registration on such National Securities Exchange as the Holder shall reasonably request, and (ii) do any and all other acts and things that may reasonably be necessary or appropriate to enable the Holder to consummate a public sale of such

2

AMENDMENT NO. 1

TO

FOURTH AMENDED AND RESTATED AGREEMENT OF LIMITED PARTNERSHIP

OF NATURAL RESOURCE PARTNERS L.P.

Partnership Securities in such states. Except as set forth in Section 7.12(d), all costs and expenses of any such registration and offering (other than the underwriting discounts and commissions, if any) shall be paid by the Partnership, without reimbursement by the Holder; provided, however, that with respect to each such registration and offering requested by Adena pursuant to this Section 7.12(a), such costs and expenses shall be paid by the Partnership only to the extent that such costs and expenses exceed $150,000.

(b) Section 7.12(b) is hereby amended and restated in its entirety as follows:

(b) If any Holder holds Partnership Securities that it desires to sell and Rule 144 of the Securities Act (or any successor rule or regulation to Rule 144) or another exemption from registration is not available to enable such Holder to dispose of the number (without limitation) of Partnership Securities it desires to sell at the time it desires to do so without registration under the Securities Act, then at the option and upon the request of the Holder, the Partnership shall file with the Commission as promptly as practicable after receiving such request, and use all reasonable efforts to cause to become effective and remain continuously effective, supplemented and amended to the extent necessary to ensure that it is available until all Partnership Securities covered by such shelf registration statement have been sold, a “shelf” registration statement covering the Partnership Securities specified by the Holder on an appropriate form under Rule 415 under the Securities Act, or any similar rule that may be adopted by the Commission; provided, however, that after November 1, 2011, the Partnership shall not be required to effect more than three registrations pursuant to Section 7.12(a) and Section 7.12(b) at the request of Adena or more than one registration pursuant to Section 7.12(a) and Section 7.12(b) at the request of each of Western Pocahontas, Great Northern and New Gauley; and provided further, however, that if the Conflicts Committee determines in good faith that any offering under, or the use of any prospectus forming a part of, the shelf registration statement would be materially detrimental to the Partnership and its Partners because such offering or use would (x) materially interfere with a significant acquisition, reorganization or other similar transaction involving the Partnership, (y) require premature disclosure of material information that the Partnership has a bona fide business purpose for preserving as confidential or (z) render the Partnership unable to comply with requirements under applicable securities laws, then the Partnership shall have the right to suspend such offering or use for a period of not more than six months after receipt of the Holder’s request, such right pursuant to Section 7.12(a) or this Section 7.12(b) not to be utilized more than twice in any twelve-month period. Except as provided in the preceding sentence, the Partnership shall be deemed not to have used all reasonable efforts to keep the shelf registration statement effective during the applicable period if it voluntarily takes any action that would result in Holders of Partnership Securities covered thereby not being

3

AMENDMENT NO. 1

TO

FOURTH AMENDED AND RESTATED AGREEMENT OF LIMITED PARTNERSHIP

OF NATURAL RESOURCE PARTNERS L.P.

able to offer and sell such Partnership Securities at any time during such period, unless such action is required by applicable law. In connection with any shelf registration pursuant to this Section 7.12(b), the Partnership shall (i) promptly prepare and file (A) such documents as may be necessary to register or qualify the securities subject to such shelf registration under the securities laws of such states as the Holder shall reasonably request; provided, however, that no such qualification shall be required in any jurisdiction where, as a result thereof, the Partnership would become subject to general service of process or to taxation or qualification to do business as a foreign corporation or partnership doing business in such jurisdiction solely as a result of such shelf registration, and (B) such documents as may be necessary to apply for listing or to list the Partnership Securities subject to such shelf registration on such National Securities Exchange as the Holder shall reasonably request, and (ii) do any and all other acts and things that may be necessary or appropriate to enable the Holder to consummate a public sale of such Partnership Securities in such states. Except as set forth in Section 7.12(d), all costs and expenses of any such shelf registration and offering (other than the underwriting discounts and commissions, if any) shall be paid by the Partnership, without reimbursement by the Holder; provided, however, that with respect to each such shelf registration and offering requested by Adena pursuant to this Section 7.12(b), such costs and expenses shall be paid by the Partnership only to the extent that such costs and expenses exceed $150,000.

(c) Section 7.12(e) is hereby amended to include the phrase “(and any of the General Partner’s Affiliates including Adena)” in lieu of the parenthetical in the first sentence thereof.

Section 2. Ratification of Partnership Agreement. Except as expressly modified and amended herein, all of the terms and conditions of the Partnership Agreement shall remain in full force and effect.

Section 3. Governing Law. This Amendment No. 1 will be governed by and construed in accordance with the laws of the State of Delaware.

[The Remainder Of This Page Is Intentionally Blank]

4

AMENDMENT NO. 1

TO

FOURTH AMENDED AND RESTATED AGREEMENT OF LIMITED PARTNERSHIP

OF NATURAL RESOURCE PARTNERS L.P.

IN WITNESS WHEREOF, the General Partner has executed this Amendment No. 1 as of the date first set forth above.

SIGNATURE PAGE

AMENDMENT NO. 1

TO

FOURTH AMENDED AND RESTATED AGREEMENT OF LIMITED PARTNERSHIP

OF NATURAL RESOURCE PARTNERS L.P.