<PAGE>
                                                                    Exhibit 4.12

                                                                  EXECUTION COPY


                          REGISTRATION RIGHTS AGREEMENT

      This REGISTRATION RIGHTS AGREEMENT, dated as of December 22, 2003 (this
"Agreement"), is entered into by and between Ark Land Company, a Delaware
corporation ("Ark"), and Natural Resource Partners L.P., a Delaware limited
partnership ("NRP").

                                    RECITALS:


      WHEREAS, Ark received 4,796,920 Common Units (the "Ark Common Units") of
NRP in connection with the contribution of certain properties to NRP at the time
of its initial public offering;

      WHEREAS, pursuant to Section 7.12 of that certain First Amended and
Restated Agreement of Limited Partnership of Natural Resource Partners L.P.,
dated as of October 17, 2002, by and among NRP (GP) LP, a Delaware limited
partnership ("NRP GP"), GP Natural Resource Partners LLC, a Delaware limited
liability company ("GP NRP"), and the other parties thereto (the "NRP
Partnership Agreement"), Ark, an Affiliate (as defined in the NRP Partnership
Agreement) of the general partner of NRP, received certain registration rights;

      WHEREAS, as a result of that certain Purchase and Sale Agreement, dated as
of December 22, 2003, between Ark and Robertson Coal Management LLC, a Delaware
limited liability company, Ark is no longer an Affiliate (as defined in the NRP
Partnership Agreement) of the general partner of NRP, and therefore, no longer
is entitled to registration rights under the NRP Partnership Agreement;

      WHEREAS, to facilitate the orderly sale of the Ark Common Units by Ark,
NRP is willing to provide certain registration rights with respect thereto; and

      WHEREAS, NRP and Ark deem it to be in their respective best interests to
enter into this Agreement to set forth such registration rights.

      NOW, THEREFORE, in consideration of the premises and mutual covenants and
obligations hereinafter set forth, and other good and valuable consideration,
the receipt and sufficiency of which are hereby acknowledged, and intending to
be legally bound, the parties hereto hereby agree as follows:

      Section 1. Definitions. Except as stated otherwise herein, the following
terms have the following meanings:


      "Affiliate" means, with respect to any Person, (i) a director or executive
officer of such Person, or (ii) any other Person that, directly or indirectly
through one (1) or more intermediaries, controls, is controlled by, or is under
common control with such Person. For purposes of this definition, the term
"control" means the possession, directly or indirectly, of the power to direct
the management and policies of a Person, whether through the ownership of voting
securities, by contract or otherwise.

      "Business Day" means a day that is not a Saturday, Sunday or other day on
which banks in Houston, Texas or New York, New York are authorized or obligated
to close.




<PAGE>

      "Commission" means the Securities and Exchange Commission or any other
governmental body or agency succeeding to the functions thereof.

      "Common Units" means the common units representing limited partnership
interests in NRP.

      "Conflicts Committee" means the Conflicts Committee or other similar
committee of GP NRP, the general partner of NRP (GP) (which is the general
partner of NRP).

      "Equity Equivalents" means securities that are convertible, exchangeable
or exercisable for or into Common Units.

      "Exchange Act" means the Securities Exchange Act of 1934, as amended, or
any successor federal statute, and the rules and regulations of the Commission
promulgated thereunder, all as the same shall be in effect from time to time.

      "Person" shall be construed broadly and shall include an individual, a
partnership, a corporation, an association, a joint stock company, a limited
liability company, a trust, a joint venture, an unincorporated organization and
a governmental entity or any department, agency or political subdivision
thereof.

      "Public Offering" means a public offering of Common Units or Equity
Equivalents pursuant to a registration statement declared effective under the
Securities Act, except that a Public Offering shall not include an offering made
in connection with a business combination or otherwise on Form S-4 under the
Securities Act (or any successor form) or an employee benefit plan or otherwise
on Form S-8 under the Securities Act (or any successor form) or dividend
reinvestment plan on Form S-3 under the Securities Act (or any successor form).

      "Registrable Securities" shall mean (i) Ark Common Units; (ii) any Common
Units or other securities issued as a dividend or other distribution with
respect to or in exchange for or in replacement of the Ark Common Units and
(iii) any then outstanding securities into which the Ark Common Units shall have
been changed by any reclassification or recapitalization of the Ark Common Units
or otherwise, in each case to the extent and only to the extent such securities
are held by the Unitholders; provided, however, that as to any particular
Registrable Securities, once issued, such securities shall cease to be
Registrable Securities if (A) a registration statement with respect to the sale
of such securities shall have become effective under the Securities Act and such
securities shall have been disposed of by the holder in accordance with such
registration statement, (B) such securities shall have been sold pursuant to
Rule 144 (as defined below) or pursuant to another exemption from registration
under the Securities Act, (C) as to the provisions of Section 3 hereof only, at
any time the Registrable Securities owned by a Unitholder (together with all
Registrable Securities owned by its Affiliates) represent less than 1% of the
then outstanding Common Units (adjusted to reflect splits, reclassifications and
similar events) and the holder of such securities may sell such securities
pursuant to paragraph (k) of Rule 144 and without any limitation as to timing,
volume or manner of sale, or (D) such securities shall have ceased to be
outstanding.



                                       2
<PAGE>

      "Requesting Unitholders" means, with respect to any request for
registration hereunder, the Unitholders that have requested such registration
under Section 2 or Section 3 hereof, as the case may be.

      "Required Unitholders" means, as of the date of any determination thereof,
the Unitholders that hold Registrable Securities representing at least a
majority (by number of units) of the Registrable Securities, on a fully diluted
basis, then held by all of the Unitholders.

      "Rule 144" means Rule 144 promulgated under the Securities Act or any
successor rule thereto or any complementary rule thereto (such as Rule 144A).

      "Securities Act" means the Securities Act of 1933, as amended, or any
successor Federal statute, and the rules and regulations of the Commission
thereunder, all as the same shall be in effect from time to time.

      "Unitholders" means, collectively, (i) Ark and (ii) any Persons which, in
the future, may become parties to this Agreement pursuant to Section 12(e)
hereof.

      "Unitholders' Counsel" means one (1) counsel chosen by the Requesting
Unitholders.

      Section 2. Required Registration.


      (a) Subject to Section 2(b) hereof and commencing on February 1, 2004, if
(i) NRP shall be requested by the Required Unitholders to effect the
registration under the Securities Act of Registrable Securities, and (ii) Rule
144 or another exemption from registration is not available to enable the
Required Unitholders to dispose of the number of Registrable Securities they
desire to sell at the time they desire to do so without registration under the
Securities Act, then NRP shall prepare and file with the Commission the
registration statement covering such Registrable Securities. A request for a
registration under this Section 2 shall: (i) specify the Registrable Securities
intended to be offered and sold by the Required Unitholders, (ii) express each
such Required Unitholders' present intent to offer such Registrable Securities
for distribution, (iii) describe the intended nature and method of the proposed
offer and sale of Registrable Securities, and (iv) contain the undertakings of
each such Required Unitholder to provide all such information and materials and
take all action as may be required to permit NRP to comply with all applicable
requirements in connection with the registration of such Registrable Securities.

      (b) Anything contained in Section 2(a) hereof notwithstanding, NRP shall
not be obligated to effect any registration of Registrable Securities under the
Securities Act pursuant to Section 2(a) hereof, except in accordance with the
following provisions:

            (i) NRP shall not be obligated to prepare and file and use its
      commercially reasonable efforts to cause to become effective, within the
      meaning of clause (iv) below, a registration statement pursuant to Section
      2(a) hereof until February 1, 2004;

            (ii) NRP shall not be obligated to prepare and file and use its
      commercially reasonable efforts to cause to become effective, within the
      meaning


                                       3
<PAGE>

      of clause (iv) below, more than one (1) registration statement pursuant to
      Section 2(a) hereof;

            (iii) If the Conflicts Committee determines in its good faith
      judgment that a postponement of the filing or effectiveness of the
      requested registration for up to six months from the date of such request
      would be in the best interest of NRP and its Partners (as such term is
      defined in the Partnership Agreement) due to a pending transaction,
      investigation or event, NRP upon prompt written notice to the Requesting
      Unitholders, may delay the filing or effectiveness of such Registration
      statement for such period of time.

            (iv) At any time before the registration statement covering
      Registrable Securities becomes effective, the Requesting Unitholders that
      requested such registration may request NRP to withdraw or not to file the
      registration statement. In that event, if such request of withdrawal shall
      not have been caused by, or made in response to, a material adverse change
      in the business, properties, condition, financial or otherwise, or
      operations of NRP occurring on or after the date of such request, the
      demand registration right shall be deemed to have been effected, as
      provided in clause (ii) above, unless the Requesting Unitholders shall pay
      to NRP the expenses incurred by NRP in connection with such registration
      statement through the date of such request, in which case no such demand
      registration right shall be deemed to have been effected.

      (c) Subject to Section 2(b)(iv) hereof, no registration shall be deemed to
have been requested or effected for any purposes under this Section 2: (A)
unless a registration statement with respect thereto has become effective; (B)
if, after it has become effective, any stop order, injunction or other order or
requirement of the Commission or any other governmental agency or court, for any
reason, affecting any of the Registrable Securities covered by such registration
statement, is issued by the Commission or other governmental agency or court and
not withdrawn within ten (10) Business Days; (C) if the conditions to closing
specified in the purchase agreement or underwriting agreement entered into in
connection with such registration are not satisfied by reason of a failure by or
inability of NRP to satisfy any of such conditions, or the occurrence of an
event outside the control of the relevant Requesting Unitholders; or (D) if the
request for withdrawal made by the Requesting Unitholders pursuant to Section
2(b)(iv) hereof shall have been caused by, or made in response to, the material
adverse change in the business properties, condition, financial or otherwise, or
operations of NRP.

      (d) If a registration effected pursuant to this Section 2 is for an
underwritten Public Offering, then NRP may include in such registration the
number of securities (for its own account or the account of any securityholder),
which in the opinion of such underwriters can be sold without adversely
affecting the proposed offering or the offering price, provided the number of
Registrable Securities requested by the Requesting Unitholders to be included in
such registration shall not be reduced.

      Section 3. Piggyback Registration.




                                       4
<PAGE>

      (a) With respect to any Registrable Securities, if at any time after May
1, 2004, NRP proposes for any reason to register any Common Units or Equity
Equivalents (other than in connection with a business acquisition or otherwise
on Form S-4 under the Securities Act (or any successor form) or an employee
benefit plan or otherwise on Form S-8 under the Securities Act (or any successor
form)) then it shall promptly give written notice at least fifteen (15) Business
Days before the filing date to each of the holders of Registrable Securities of
its intention to so register such Common Units or Equity Equivalents and, upon
the written request, delivered to NRP within ten (10) Business Days after
receipt of any such notice by NRP, of the Unitholders to include in such
registration Registrable Securities (which request shall specify the number of
Registrable Securities proposed to be included in such registration), NRP shall
cause all such Registrable Securities to be included in such registration on the
same terms and conditions as the Common Units or Equity Equivalents otherwise
being sold in such registration, subject to the limitations set forth herein.

      (b) If a registration referred to in Section 3(a) hereof relates to an
underwritten Public Offering on behalf of NRP, and the managing underwriters
advise NRP in writing that the inclusion of all Registrable Securities requested
to be included in such registration would materially and adversely affect the
proposed offering or the offering price, NRP will include in such registration:
(i) first, all securities NRP proposes to sell, and (ii) second, (A) all
Registrable Securities that the Requesting Unitholders request to be included in
the underwritten Public Offering, plus (B) such other securities (provided such
securities are of the same class as the securities being sold by NRP) as are
requested to be included in such registration by the holders thereof pursuant to
registration rights granted by NRP, all of which shall be allocated pro rata
among the holders of such Registrable Securities and other securities on the
basis of the dollar amount or number of Registrable Securities and other
securities requested to be included therein by each such holder of Registrable
Securities or other securities. If a registration referred to in Section 3(a)
hereof relates to an underwritten secondary registration on behalf of holders of
NRP's securities (other than holders of Registrable Securities in their capacity
as such), and the managing underwriters advise NRP in writing that in their
opinion the securities requested to be included in such registration exceeds the
securities which can be sold in such offering without adversely affecting the
offering or the offering price, NRP will include in such registration, (i)
first, the securities which in the opinion of such underwriters can be sold
without adversely affecting the offering or the offering price of the securities
intended to be included therein on behalf of the other holders of NRP's
securities, allocated among the holders of such securities in such proportions
as NRP and such holders may agree, and (ii) to the extent of the balance, if
any, the Registrable Securities requested to be included in such registration,
allocated pro rata among the holders of such Registrable Securities on the basis
of the securities requested to be included therein by each such holder.

      (c) If the registration referred to in Section 3(a) hereof involves an
underwritten offering, the right of any Unitholder to include any Registrable
Securities in such registration pursuant to this Section 3 shall be conditioned
upon such Unitholders' participation in such underwritten offering. The
Unitholders proposing to include their Registrable Securities pursuant to this
Section 3 shall enter into an underwriting agreement in customary form with the
underwriter or underwriters selected for such underwriting by NRP.



                                       5
<PAGE>

      (d) Notwithstanding anything to the contrary in this Section 3, if a
registration referred to in Section 3(a) hereof relates to an underwritten
offering of a class of securities of NRP different from the Registrable
Securities proposed to be included in such offering and the managing
underwriters advise that in their opinion Registrable Securities of a different
class cannot be included in such offering without adversely affecting the
offering or the offering price, then the holders of the Registrable Securities
shall not be entitled to include Registrable Securities in such registration.

      (e) NRP shall have the right to terminate any proposed registration under
this Section 3 at any time without any obligation to the Requesting Unitholders
requesting inclusion in such registration under this Section 3.

      Section 4. Holdback Agreement.


      (a) If (i) NRP at any time shall register Common Units or Equity
Equivalents under the Securities Act (including any registration pursuant to
Section 3 hereof) for sale in an underwritten Public Offering, (ii) NRP shall
have received a request from Unitholders pursuant to Section 3(a) hereof for
inclusion of Registrable Securities in such underwritten Public Offering and
(iii) any such Registrable Securities requested to be included in such
underwritten Public Offering shall be so included, then to the extent requested
by the underwriters for such offering, the Unitholders shall not sell, make any
short sale of, grant any option for the purchase of, or otherwise dispose of,
directly or indirectly, any Registrable Securities (other than those Registrable
Securities included in such registration) without the prior written consent of
NRP, for a period designated by the managing underwriter in writing to the
Unitholders, which period shall begin not more than seven (7) days prior to the
effectiveness of the registration statement pursuant to which such Public
Offering shall be made (or within seven (7) days prior to the execution of the
applicable underwriting agreement in the case of an offering pursuant to Rule
415) and shall not last more than ninety (90) days after the closing of such
Public Offering or such shorter holdback period to which NRP or other
unitholders of NRP holding at least ten percent (10%) of the Common Units of NRP
(on a fully diluted basis) are subject. The Requesting Unitholders will enter
into agreements with the underwriters to the foregoing effect.

      (b) If, at any time, NRP is requested by the Requesting Unitholders to
register Registrable Securities pursuant to Section 2(a) hereof under the
Securities Act for sale in an underwritten Public Offering, then to the extent
requested by the underwriters for such offering NRP shall not sell, make any
short sale of, grant any option (other than under compensatory option or benefit
plans of NRP or its Affiliates) for the purchase of, or otherwise dispose of,
directly or indirectly, any securities similar to those being registered or any
Equity Equivalents, without the prior written consent of the managing
underwriter, for a period designated by the managing underwriter in writing to
NRP, which period shall begin not more than seven (7) days prior to the
effectiveness of the registration statement pursuant to which such public
offering shall be made (or within seven (7) days prior to the execution of the
applicable underwriting agreement in the case of an offering pursuant to Rule
415) and shall not last more than ninety (90) days after the closing of such
Public Offering or such shorter holdback period to which the Unitholders are
then subject.



                                       6
<PAGE>

      Section 5. Preparation and Filing.


      (a) If and whenever NRP is under an obligation pursuant to the provisions
of this Agreement to effect the registration of any Registrable Securities, NRP
shall:

            (i) cause a registration statement that registers such Registrable
      Securities to be filed with the Commission as promptly as practicable
      following the request delivered pursuant to Section 2 hereof, but in any
      event within sixty (60) days from the date of such request; provided,
      however, that if the filing of such registration statement shall be
      delayed as provided in Section 2 (b)(iii), such registration statement
      shall be filed within 15 days of the date upon which the Conflicts
      Committee shall determine such conflict shall no longer exist;

            (ii) use its commercial reasonable efforts to cause such
      registration statement to become effective as promptly as practicable, but
      in no event later than ninety (90) days following the filing of the
      registration statement pursuant to Section 5(a)(i) hereof;

            (iii) cause such registration statement to remain effective for a
      period (the "Registration Period") of one-hundred eighty (180) days (or
      such extended period pursuant to clause (viii) below) or until all of such
      Registrable Securities have been disposed of (if earlier);


            (iv) furnish, at least five (5) Business Days before filing a
      registration statement that registers such Registrable Securities, a
      prospectus relating thereto or any amendments or supplements relating to
      such a registration statement or prospectus, to Unitholders' Counsel,
      copies of all such documents proposed to be filed (it being understood
      that such five-Business-Day period need not apply to successive drafts of
      the same document proposed to be filed so long as such successive drafts
      are supplied to Unitholders' Counsel in advance of the proposed filing by
      a period of time that is customary and reasonable under the
      circumstances);

            (v) prepare and file with the Commission such amendments and
      supplements to such registration statement and the prospectus used in
      connection therewith as may be necessary to keep such registration
      statement effective at all times during the Registration Period and to
      comply with the provisions of the Securities Act with respect to the sale
      or other disposition of such Registrable Securities;

            (vi) notify in writing Unitholders' Counsel promptly of (A) the
      receipt by NRP of any notification with respect to any comments by the
      Commission with respect to such registration statement or prospectus or
      any amendment or supplement thereto or any request by the Commission for
      the amending or supplementing thereof or for additional information with
      respect thereto, (B) the receipt by NRP of any notification with respect
      to any stop order issued or threatened to be issued by the Commission
      suspending the effectiveness


                                       7
<PAGE>

      of such registration statement or prospectus or any amendment or
      supplement thereto or the initiation or threatening of any proceeding for
      that purpose and (C) the receipt by NRP of any notification with respect
      to the suspension of the qualification of such Registrable Securities for
      sale in any jurisdiction or the initiation or threatening of any
      proceeding for such purposes;

            (vii) use its commercially reasonable efforts to register or qualify
      such Registrable Securities as promptly as practicable under such other
      securities or blue sky laws of such jurisdictions as the holders of such
      Registrable Securities reasonably request and to keep such registration
      and qualification in effect for so long as such registration statement
      remains in effect and to do any and all other acts and things which may be
      reasonably necessary or advisable to enable the holders of such
      Registrable Securities to consummate the disposition in such jurisdictions
      of the Registrable Securities owned by the holders of such Registrable
      Securities; provided, however, that NRP will not be required to qualify
      generally to do business or consent to general service of process or
      taxation in any jurisdiction where it would not otherwise be required to
      do so but for this clause (v);

            (viii) furnish, without charge, to the holders of such Registrable
      Securities such number of copies of such registration statement,
      prospectus, including a preliminary prospectus, in conformity with the
      requirements of the Securities Act, and such other documents (including
      exhibits thereto and documents incorporated by reference therein) as such
      holders may reasonably request in order to facilitate the public sale or
      other disposition of such Registrable Securities;

            (ix) use its commercially reasonable efforts to cause such
      Registrable Securities to be registered with or approved by such other
      governmental agencies or authorities or self-regulatory organizations as
      may be necessary by virtue of the business and operations of NRP to enable
      the holders of such Registrable Securities to consummate the disposition
      of such Registrable Securities;

            (x) notify in writing holders of such Registrable Securities on a
      timely basis at any time when a prospectus relating to such Registrable
      Securities is required to be delivered under the Securities Act during the
      Registration Period of the happening of any event as a result of which the
      prospectus included in such registration statement, as then in effect,
      includes an untrue statement of a material fact or omits to state a
      material fact required to be stated therein or necessary to make the
      statements therein not misleading in light of the circumstances then
      existing and, at the request of the holders of such Registrable
      Securities, prepare and furnish to such holders a reasonable number of
      copies of a supplement to or an amendment of such prospectus as may be
      necessary so that, as thereafter delivered to the offerees and purchasers
      of such units, such prospectus shall not include an untrue statement of a
      material fact or omit to state a material fact required to be stated
      therein or necessary to make the statements therein not


                                       8
<PAGE>

      misleading in light of the circumstances then existing; provided, however,
      that the Registration Period shall be deemed to be extended by the number
      of days constituting the period commencing on and including the date of
      the giving of such notice to such seller and ending on and including the
      date when NRP made available to such seller an amended or supplemented
      prospectus;

            (xi) in the case of an underwritten offering, use its commercially
      reasonable efforts to obtain from its independent certified public
      accountants "comfort" letters in customary form and at customary times and
      covering matters of the type customarily covered by comfort letters;

            (xii) in the case of an underwritten offering, (A) use its
      commercially reasonable efforts to obtain from its counsel an opinion or
      opinions in customary form to the underwriters and the holders of such
      Registrable Securities and (B) to enter into a customary underwriting
      agreement and make representations and warranties to the underwriters, in
      form, substance and scope as are customarily made by issuers to
      underwriters in comparable underwritten offerings;

            (xiii) provide a transfer agent and registrar (which may be the same
      entity and which may be NRP) for such Registrable Securities;

            (xiv) if required, issue to any underwriter to which the holders of
      Registrable Securities may sell Common Units in such offering certificates
      evidencing such Registrable Securities;

            (xv) use its commercially reasonable efforts to list such
      Registrable Securities on the New York Stock Exchange or such other
      securities exchange on which the Common Units are traded;

            (xvi) use all reasonable efforts to obtain the lifting at the
      earliest possible time of any stop order suspending the effectiveness of
      such registration statement or of any order preventing or suspending the
      use of any preliminary prospectus included therein; and

            (xvii) use its commercially reasonable efforts to take all other
      steps necessary to effect the registration of such Registrable Securities
      contemplated hereby.

      (b) Each holder of such Registrable Securities, upon receipt of any notice
from NRP of any event of the kind described in Section 5(a)(viii) hereof, shall
forthwith discontinue disposition of such Registrable Securities pursuant to the
registration statement covering such Registrable Securities until such holder's
receipt of the copies of the supplemented or amended prospectus contemplated by
Section 5(a)(viii) hereof, and, if so directed by NRP, such holder shall deliver
to NRP all copies, other than permanent file copies then in such holder's
possession, of the prospectus covering such Registrable Securities at the time
of receipt of such notice.



                                       9
<PAGE>

      (c) With respect to a request pursuant to Section 2(a) hereof, the
Requesting Unitholders shall choose the managing underwriter, provided that the
managing underwriter is reasonably acceptable to NRP. In either case, the form
of underwriting agreement shall be reasonably acceptable to NRP.

      (d) NRP may require each seller of Registrable Securities as to which any
registration is being effected hereunder to furnish to NRP such information and
complete such questionnaires regarding the seller and the distribution of such
securities as NRP may from time to time reasonably request.

      Section 6. Expenses. All expenses (other than as provided in the last
sentence of this Section 6) incident to the registration of Registrable
Securities pursuant to Section 2 hereof, including, without limitation, the fees
and expenses of the underwriters (to the extent applicable), all salaries and
expenses of NRP's officers and employees performing legal or accounting duties,
the expense of any annual audit or quarterly review, the expense of any
liability insurance, all registration and filing fees, the expense and fees for
listing securities on one (1) or more securities exchanges, the fees and
expenses of complying with securities and blue sky laws, printing expenses,
messenger and delivery expenses, fees and expenses of NRP's counsel and
accountants, and the reasonable fees and expenses of one (1) counsel to the
Unitholders (all such expenses being herein called "Registration Expenses"),
shall be borne by NRP (subject to Section 2(b)(iv) hereof). All underwriting
discounts and selling commissions applicable to the Registrable Securities and
the fees and expenses of any counsel to the Unitholders not provided for in the
above definition of Registration Expenses shall be borne by the holders selling
such Registrable Securities, in proportion to the number of such Registrable
Securities sold by each such holder.

      Section 7. Indemnification.


      (a) In connection with any registration of any Registrable Securities
under the Securities Act pursuant to this Agreement, NRP shall indemnify and
hold harmless, to the fullest extent permitted by law, the holders of
Registrable Securities, each other Person, if any, who controls any such holder
of Registrable Securities within the meaning of the Securities Act or the
Exchange Act, and each of their respective directors, officers and agents,
against any and all losses, claims, damages or liabilities, joint or several (or
actions or threatened actions in respect thereof), to which any of the foregoing
Persons may become subject under the Securities Act or otherwise, insofar as
such losses, claims, damages or liabilities (or actions or threatened actions in
respect thereof) arise out of or are based upon (i) an untrue statement or
allegedly untrue statement of a material fact contained in the registration
statement under which such Registrable Securities were registered under the
Securities Act, any preliminary prospectus or final prospectus contained therein
or otherwise filed with the Commission, any amendment or supplement thereto or
(ii) the omission or alleged omission to state therein a material fact required
to be stated therein or necessary to make the statements therein not misleading
or, with respect to any prospectus, necessary to make the statements therein in
light of the circumstances under which they were made not misleading. NRP shall
reimburse each holder of Registrable Securities and each such controlling Person
for any expenses (including reasonable attorneys' fees, disbursements and
expenses as incurred) reasonably incurred by any of them in connection with
investigating or defending against any such loss, claim, damage, liability,
action or


                                       10
<PAGE>

threatened action. Notwithstanding the foregoing provisions of this Section 7,
NRP shall not be liable to any such indemnified Person in any such case to the
extent that any such loss, claim, damage, liability, action or threatened action
(including any reasonable legal or other fees, disbursements and expenses
incurred) arises out of or is based upon an untrue statement or allegedly untrue
statement or omission or alleged omission made in said registration statement,
preliminary prospectus, final prospectus, amendment or supplement in reliance
upon and in conformity with written information furnished to NRP by or on behalf
of a holder of Registrable Securities specifically for use in the preparation
thereof. The foregoing indemnity agreements of NRP and holders of Registrable
Securities are subject to the condition that, insofar as they relate to any
untrue statement, allegedly untrue statement, omission or alleged omission made
in a preliminary prospectus but eliminated or remedied in the amended prospectus
on file with the Commission at the time the registration statement in question
becomes effective or the amended prospectus filed with the Commission pursuant
to Commission Rule 424(b) (the "Final Prospectus"), such indemnity agreement
shall not inure to the benefit of any Person if a copy of the Final Prospectus
was timely furnished to the indemnified party and was not furnished to the
Person asserting the loss, liability, claim or damage at or prior to the time
such action is required by the Securities Act.

      (b) In connection with any registration of Registrable Securities under
the Securities Act pursuant to this Agreement, each holder of Registrable
Securities shall severally and not jointly indemnify and hold harmless, in the
same manner and to the same extent as set forth in Section 7(a) hereof, NRP,
each director of the general partner of NRP's general partner, each officer of
the general partner of NRP's general partner who shall sign such registration
statement and each Person who controls any of the foregoing Persons (within the
meaning of the Securities Act), against any losses, claims, damages or
liabilities, joint or several (or actions or threatened actions in respect
thereof), to which any of the foregoing Persons may become subject under the
Securities Act or otherwise, insofar as such losses, claims, damages or
liabilities (or actions or threatened actions in respect thereof) arise out of
or are based upon any statement or omission from such registration statement,
any preliminary prospectus or final prospectus contained therein or otherwise
filed with the Commission, any amendment or supplement thereto, if such
statement or omission was made in reliance upon and in conformity with written
information furnished to NRP by such holder with respect to such holder
specifically for use in connection with the preparation of such registration
statement, preliminary prospectus, final prospectus, amendment or supplement;
provided, however, that the maximum amount of liability in respect of such
indemnification shall be limited, in the case of each seller of Registrable
Securities, to an amount equal to the net proceeds actually received by such
seller from the sale of Registrable Securities effected pursuant to such
registration.

      (c) Promptly after receipt by an indemnified party of notice of the
commencement of any action involving a claim referred to in the preceding
paragraphs of this Section 7, such indemnified party will, if a claim in respect
thereof is to be made against an indemnifying party, give written notice to the
indemnifying party of the commencement of such action. In case any such action
is brought against an indemnified party, the indemnifying party will be entitled
to participate in and to assume the defense thereof, jointly with any other
indemnifying party similarly notified to the extent that it may wish, with
counsel reasonably satisfactory to such indemnified party, and after notice from
the indemnifying party to such indemnified party of its election so to assume
the defense thereof, (i) the indemnified party shall reasonably cooperate


                                       11
<PAGE>

with the indemnifying party and its counsel in the defense of such claim, and
(ii) the indemnifying party shall not be responsible for any legal or other
fees, disbursements and expenses subsequently incurred by the indemnified party
in connection with the defense thereof; provided, however, that if any
indemnified party shall have reasonably concluded that there may be one (1) or
more legal or equitable defenses available to such indemnified party which are
additional to or conflict with those available to the indemnifying party, the
indemnifying party shall not have the right to assume the defense of such action
on behalf of such indemnified party and such indemnifying party shall reimburse
such indemnified party and any Person controlling such indemnified party for
that portion of the fees, disbursements and expenses of not more than one (1)
counsel retained by the indemnified party in connection with the matters covered
by the indemnity agreement provided in this Section 7; provided, that no
indemnifying party shall, in connection with any such suit, be liable under this
subsection for the fees and expenses of more than one (1) separate firm for all
indemnified parties. No indemnifying party shall be liable for any compromise or
settlement of any such action effected without its consent, such consent not to
be unreasonably withheld. No indemnifying party, in the defense of any such
claim or suit, shall, except with the consent of each indemnified party, which
shall not be unreasonably withheld, consent to any compromise or settlement
which does not include as an unconditional term thereof the giving by the
claimant to such indemnified party of a release from all liability in respect of
such claim or suit.

      (d) If the indemnification provided for in this Section 7 is unavailable
to an indemnified party hereunder with respect to any loss, claim, damage,
liability, action or threatened action referred to herein, then the indemnifying
party, in lieu of indemnifying such indemnified party hereunder, shall
contribute to the amounts paid or payable by such indemnified party as a result
of such loss, claim, damage, liability, action or threatened action in such
proportion as is appropriate to reflect the relative fault of the indemnifying
party on the one hand and of the indemnified party on the other in connection
with the statements or omissions which resulted in such loss, claim, damage,
liability, action or threatened action as well as any other relevant equitable
considerations. The relative fault of the indemnifying party and of the
indemnified party shall be determined by reference to, among other things,
whether any statement or omission, including any untrue or alleged untrue
statement of a material fact or the omission or alleged omission to state a
material fact relates to information supplied by the indemnifying party or by
the indemnified party and the parties' relative intent, knowledge, access to
information and opportunity to correct or prevent such statement or omission;
provided, however, that the maximum amount of liability in respect of such
contribution shall be limited, in the case of each seller of Registrable
Securities, to an amount equal to the net proceeds actually received by such
seller from the sale of Registrable Securities effected pursuant to such
registration. The amount paid or payable by a party under this Section 7(d) as a
result of the loss, claim, damage, liability, action or threatened action
referred to above shall be deemed to include any legal or other fees (subject to
the limitations set forth in Section 7(c) hereof), disbursements and expenses
reasonably incurred by such party in connection with any investigation or
proceeding. The parties hereto agree that it would not be just and equitable if
contributions pursuant to this Section 7(d) were to be determined by pro rata
allocation or by any method of allocation which does not take account of the
equitable considerations referred to in the first and second sentences of this
Section 7(d). No Person guilty of fraudulent misrepresentation (within the
meaning of Section 11(f) of the Securities Act) shall be entitled to
contribution from any Person who was not guilty of such fraudulent
misrepresentation.



                                       12
<PAGE>

      (e) The provisions of this Section 7 shall be in addition to any other
liability which any indemnifying party may have to any indemnified party and
shall survive the termination of this Agreement.

      Section 8. Underwriting Agreement. To the extent that the holders of
Registrable Securities participating in any underwritten offering shall enter
into an underwriting or similar agreement that contains provisions which
conflict with any provision of Section 7 hereof, as between NRP and such holders
of Registrable Securities, the provisions contained in Section 7 hereof shall
control.

      Section 9. Information by Holder. The Unitholders shall furnish to NRP
such written information regarding the Unitholders and the distribution proposed
by the Unitholders as NRP may reasonably request in writing and as shall be
reasonably required in connection with any registration, qualification or
compliance referred to in this Agreement.

      Section 10. Exchange Act Compliance. NRP agrees to and shall comply with
all of the reporting requirements of the Exchange Act applicable to it. Upon the
request of any holder of Registrable Securities, NRP shall deliver to such
holder a written statement as to whether it has complied with such requirements.
NRP shall cooperate with the Unitholders in supplying such information as may be
necessary for the Unitholders to complete and file any information reporting
forms presently or hereafter required by the Commission as a condition to the
availability of Rule 144.

      Section 11. Termination. Except as provided in Section 7(e) hereof, this
Agreement shall terminate and be of no further force or effect when there shall
no longer be any Registrable Securities outstanding.

      Section 12. Miscellaneous.


      (a) Notices. All notices, requests and other communications hereunder must
be in writing and will be deemed to have been duly given only if delivered
personally at by facsimile transmission or mailed (prepaid first class certified
mail, return receipt requested) to the parties at the following addresses or
facsimile numbers:


      If to NRP, to:

           Natural Resource Partners L.P.
           601 Jefferson Street, Suite 3600
           Houston, Texas 77002
           Attention:  General Counsel
           Fax No.  (713) 650-0606

      With a copy to:

           GP Natural Resource Partners LLC
           601 Jefferson Street, Suite 3600
           Houston, Texas 77002
           Attention:  General Counsel

                                       13
<PAGE>

           Fax No.  (713) 650-0606

      If to Ark or its Affiliates, to:

           Ark Land Company
           One CityPlace Drive, Suite 300
           St. Louis, Missouri 63141
           Attention: General Counsel
           Fax No.  (314) 994-2734

      With a copy to:

           Arch Coal, Inc.
           One CityPlace Drive, Suite 300
           St. Louis, Missouri 63141
           Attention: General Counsel
           Fax No.  (314) 994-2734

All such notices, requests and other communications will (i) if delivered
personally against written receipt to the address as provided in this Section,
be deemed given upon delivery, (ii) if delivered by facsimile transmission to
the facsimile number as provided in this Section, be deemed given upon receipt
or upon the next Business Day if received after normal business hours or a day
which is not a Business Day, and (iii) if delivered by mail in the manner
described above to the address as provided in this Section, be deemed given upon
receipt (in each case regardless of whether such notice is received by any other
person to whom a copy of such notice, request or other communication is to be
delivered pursuant to this Section). Any party from time to time may change its
address, facsimile number or other information for the purpose of notices to
that party by giving notice specifying such change to the other parties hereto.

      (b) Specific Performance. The parties hereto agree that in the event any
provision of this Agreement was not performed in accordance with the terms
hereof, irreparable damage would occur, and that the parties shall therefore be
entitled to specific performance of the terms hereof, in addition to any remedy
that may be available to any of them at law or equity and, to the extent
permitted by applicable law, each party waives any objection to the imposition
of such relief.

      (c) Acknowledgement. By executing this Agreement, Ark hereby acknowledges,
agrees and confirms that as a result of that certain Purchase and Sale
Agreement, dated as of December 22, 2003, between Ark and Robertson Coal
Management LLC, a Delaware limited liability company, Ark is no longer an
Affiliate (as defined in the NRP Partnership Agreement) of the general partner
of NRP, and therefore, no longer is entitled to registration rights under the
NRP Partnership Agreement.

      (d) Entire Agreement. This Agreement supersedes all prior discussions and
agreements between the parties with respect to the subject matter hereof, and
contains the sole and entire agreement between the parties hereto with respect
to the subject matter hereof.




                                       14
<PAGE>

      (e) Successors and Assigns. This Agreement shall bind and inure to the
benefit of NRP and the Unitholders and, subject to Section 12(f) hereof, the
respective successors and assigns of NRP and the Unitholders.


      (f) Assignment. Each Unitholder may assign its rights hereunder to any
Affiliate that is a purchaser or transferee of Registrable Securities; provided,
however, that (i) such transfer is otherwise effected in accordance with
applicable securities laws, (ii) such purchaser or transferee shall, as a
condition to the effectiveness of such assignment, be required to execute a
counterpart to this Agreement agreeing to be treated as a Unitholder, whereupon
such purchaser or transferee shall have the benefits of and shall be subject to
the restrictions contained in this Agreement as if such purchaser or transferee
was originally included in the definition of a Unitholder and had originally
been a party hereto and (iii) NRP is given written notice of such transfer after
such transfer, setting forth the name and address of such Affiliate assignee and
identifying the Registrable Securities with respect to which such registration
rights have been assigned. Schedule I hereto shall, from time to time, be
amended to include the name, address and numbers of Registrable Securities of
each such Unitholder.

      (g) Waiver. Any term or condition of this Agreement may be waived at any
time by the party that is entitled to the benefit thereof, but no such waiver
shall be effective unless set forth in a written instrument duly executed by or
on behalf of the party waiving such term or condition. No waiver by any party of
any term or condition of this Agreement, in any one (1) or more instances, shall
be deemed to be or construed as a waiver of the same or any other term or
condition of this Agreement on any future occasion. All remedies, either under
this Agreement or by law or otherwise afforded, will be cumulative and not
alternative.

      (h) Amendment. This Agreement may be amended, supplemented or modified
only by a written instrument duly executed by or on behalf of each party hereto.


      (i) No Third Party Beneficiary. The terms and provisions of this Agreement
are intended solely for the benefit of each party hereto and their respective
successors or permitted assigns, and it is not the intention of the parties to
confer third-party beneficiary rights upon any other Person except to the extent
such Person is expressly given rights herein.

      (j) Headings. The headings used in this Agreement have been inserted for
convenience of reference only and do not define or limit the provisions hereof.


      (k) Invalid Provisions. If any provision of this Agreement is held to be
illegal, invalid or unenforceable under any present or future law, and if the
rights or obligations of any party hereto under this Agreement will not be
materially and adversely affected thereby, (i) such provision will be fully
severable, (ii) this Agreement will be construed and enforced as if such
illegal, invalid or unenforceable provision had never comprised a part hereof,
(iii) the remaining provisions of this Agreement will remain in full force and
effect and will not be affected by the illegal, invalid or unenforceable
provision or by its severance herefrom and (iv) in lieu of such illegal, invalid
or unenforceable provision, there will be added automatically as a part of this
Agreement a legal, valid and enforceable provision as similar in terms to such
illegal, invalid or unenforceable provision as may be possible.



                                       15
<PAGE>

      (l) Governing Law. This Agreement shall be governed by and construed in
accordance with the laws of the State of Texas applicable to a contract executed
and performed in such State without giving effect to the conflicts of laws
principles thereof.


      (m) Counterparts. This Agreement may be executed in any number of
counterparts, each of which will be deemed an original, but all of which
together will constitute one and the same instrument.




                                       16
<PAGE>





      IN WITNESS WHEREOF, each of the undersigned has caused this Agreement to
be executed as of the date first written above.

                                     ARK LAND COMPANY

                                     By:     /S/ Steven E. McCurdy
                                             -----------------------------------
                                             Name:   Steven E. McCurdy
                                             Title:     President




                                     NATURAL RESOURCE PARTNERS L.P.

                                     By:    GP Natural Resource Partners LLC,
                                             its General Partner

                                     By:    /S/ Wyatt L. Hogan
                                            ------------------------------------
                                            Name:  Wyatt L. Hogan
                                            Title: Vice President and General
                                                   Counsel




                 SIGNATURE PAGE TO REGISTRATION RIGHTS AGREEMENT

<PAGE>



                                   SCHEDULE I

 Unitholders                 Number of Registrable Securities Held

 Ark Land Company            4,796,920