Portions of this exhibit indicated by ****** have been omitted pursuant to a request for

EXHIBIT 10.4

Portions of this exhibit indicated by “******” have been omitted pursuant to a request for

confidential treatment under Rule 24b-2 of the Securities Exchange Act of 1934, as

amended, and the omitted material has been separately filed with the Securities and

Exchange Commission.

AMENDED AND RESTATED EQUIPMENT LEASE AGREEMENT

(Existing Truck Unloading Facility)

THIS AMENDED AND RESTATED EQUIPMENT LEASE AGREEMENT (“Agreement”) is made on the 22^nd day of June, 2005 effective as of the 1st day of January, 2007 (the “Effective Date”), by and between Virginia Electric and Power Company, a Virginia public service corporation with its principal office located in Richmond, Virginia, trading in the Commonwealth of Virginia as “Virginia Power” and in the State of North Carolina as “North Carolina Power” (hereinafter referred to as “Virginia Power”), and Mettiki Coal, LLC, a Delaware limited liability company which has its principal office located in Tulsa, Oklahoma and which is the successor entity to Mettiki Coal Corporation (hereinafter referred to as “Mettiki”). Virginia Power and Mettiki sometimes are referred to hereinafter individually as a “party” and collectively as the “parties.”

RECITALS

WHEREAS, pursuant to the terms of that certain Lease Agreement effective January 15, 1996 (the “Existing Premises Lease Agreement”), Mettiki is the lessee of certain real estate (the “Premises”) owned by Virginia Power and located at Virginia Power’s Mt. Storm Power Station (the “Station”) located in Mt. Storm, West Virginia; and

WHEREAS, Virginia Power and Mettiki are parties to that certain Equipment Lease Agreement, effective as of January 15, 1996 (the “Existing Equipment Lease”), pursuant to which Mettiki leases to Virginia Power that certain truck unloading facility located on the Premises (the “Existing Truck Unloading Facility”); and

WHEREAS, the term of the Existing Equipment Lease is coterminous with the Existing Premises Lease Agreement; and

WHEREAS, subject to the terms and conditions of the Existing Premises Lease Agreement, the term of the Existing Premises Lease Agreement will expire at 11:59 p.m. on December 31, 2006 (the “Existing Premises Lease Expiration Time”); and

WHEREAS, Alliance Coal, LLC, a Delaware limited liability company and the parent entity of Mettiki (“Alliance Coal”), and Virginia Power have entered into that certain Agreement for the Supply of Coal dated of even date (the “Coal Supply Agreement”); and

WHEREAS, pursuant to the Coal Supply Agreement, the parties hereto have entered into that certain Amended and Restated Lease Agreement dated of even date (the “Amended and Restated Premises Lease Agreement”) pursuant to which the initial term of the Existing Premises Lease Agreement will be extended on, and subject to, the terms and conditions of the Amended and Restated Premises Lease Agreement; and

WHEREAS, subject to and the conditions set forth herein, Virginia Power and Mettiki also desire to extend the initial term of the Existing Equipment Lease after the Existing Premises Lease Expiration Time; and

NOW, THEREFORE, in consideration of the above Recitals, which are incorporated herein, and for and in consideration of the mutual covenants and agreements set forth below, the parties agree as follows:

a. During the term of this Agreement, the Existing Truck Unloading Facility shall remain the property of the Mettiki subject to any valid lien of Virginia Power. Upon expiration or termination of this Agreement, the Existing Truck Unloading Facility shall become the property of Virginia Power in accordance with the terms of the Coal Supply Agreement and the Amended and Restated Premises Lease Agreement.

a. Subject to the terms and conditions hereof, Mettiki will rent and lease to Virginia Power, and Virginia Power will rent and lease from Mettiki, the Existing Truck Unloading Facility during the term hereof. Unless otherwise agreed to by the parties, the Existing Truck Unloading Facility shall be used and operated only for the purpose of unloading coal to be delivered to the Station pursuant to the Coal Supply Agreement, and no other purpose.

b. Virginia Power shall lease the Existing Truck Unloading Facility on an “as is” basis and Mettiki shall not be obligated to make any alterations or improvements thereto prior to or after commencement of this Agreement.

c. Virginia Power’s right to use and operate the Existing Truck Unloading Facility as permitted herein may only be exercised by (i) Virginia Power and its employees, and (ii) Virginia Power agents, contractors, and subcontractors who have been approved in writing by Mettiki, such approval not to be unreasonably withheld, delayed or conditioned.

d. This Agreement shall in no way assign, encumber, lease, sublease or set over either party’s estate, interests or rights under the Existing Premises Lease Agreement or the Amended and Restated Premises Lease Agreement, as appropriate.

e. Mettiki shall operate the Existing Truck Unloading Facility as contemplated by the parties in the Coal Supply Agreement and the Ancillary Services Agreement attached as Attachment 1 to the Coal Supply Agreement.

f. Virginia Power shall be responsible for all direct costs and expenses to repair damage to the Existing Truck Unloading Facility caused by the negligence or intentional acts or omission(s) of Virginia Power and its affiliates and their respective employees, agents, contractor’s or subcontractors.

-2-

The term of this Agreement shall be coterminous with the term of the Amended and Restated Premises Lease Agreement.

Notwithstanding any other provision of this Agreement to the contrary, this Agreement shall automatically terminate upon the expiration, cancellation, or termination of the Coal Supply Agreement or the Amended and Restated Premises Lease Agreement.

Virginia Power agrees to pay to Mettiki a fixed rental fee of $****** per month (the “Fixed Monthly Fee”) for the lease to Virginia Power of the Existing Truck Unloading Facility through ******. The Fixed Monthly Fee shall be payable on the first day of each month during the term hereof commencing on the Effective Date. The invoicing and payment of the Fixed Monthly Fee will be effected in accordance with Article 6 of the Coal Supply Agreement. After ******, and continuing through the remaining term hereof, the Fixed Monthly Fee shall be zero.

Any default under this Agreement will constitute a default under the Coal Supply Agreement.

Except as otherwise provided herein, if Mettiki materially fails to comply with any of the provisions of this Agreement, and shall fail within thirty (30) days after written notice from Virginia Power to correct such noncompliance, Virginia Power may terminate this Agreement by giving written notice of termination to Mettiki. Such termination shall be effective as specified in the termination notice but not earlier than one (1) business day following Mettiki’s receipt of such notice. If Virginia Power terminates this Agreement for Mettiki’s default pursuant to this paragraph, Alliance Coal shall be deemed to be in material breach of the Coal Supply Agreement as of the date of such termination of this Agreement and Virginia Power may with respect to the Coal Supply Agreement exercise all remedies available to it at law, in equity or under the Coal Supply Agreement, including Virginia Power’s operation of the Existing Truck Unloading Facility as provided in the Coal Supply Agreement. Termination pursuant to the provisions of this paragraph shall not constitute a waiver of any other right or remedy Virginia Power may have under this Agreement.

Except as otherwise provided herein, if Virginia Power materially fails to comply with any of the provisions of this Agreement, and shall fail within thirty (30) days after written notice from Mettiki to correct such noncompliance, Mettiki may terminate this Agreement by giving written notice of termination to Virginia Power. Such termination shall be effective as specified in the termination notice but not earlier than one (1)

-3-

business day following Virginia Power’s receipt of such notice. If Mettiki terminates this Agreement for Virginia Power’s default pursuant to this paragraph Mettiki may exercise all remedies available to it at law, in equity or under the Coal Supply Agreement. Termination pursuant to the provisions of this paragraph shall not constitute a waiver of any other right or remedy Mettiki may have under this Agreement.

By written notice to Mettiki, Virginia Power may designate an agent for the purposes of administering this Agreement on its behalf.

Article 10 of the Coal Supply Agreement is hereby incorporated into this Agreement. In addition, except as expressly otherwise provided in this Agreement or the Coal Supply Agreement, Virginia Power shall not be liable to Mettiki for injury or death of persons or damage to property arising on account of any latent or patent defects in the Existing Truck Unloading Facility. Virginia Power shall not be liable for any losses, claims or liabilities for loss of or damage to the Existing Truck Unloading Facility as the result of the negligence or willful misconduct of Mettiki, its agents, contractors, or subcontractors.

Mettiki shall obtain and maintain, and require its contractors and subcontractors to obtain and maintain, all policies and coverage’s of insurance as required under Section 12.10 of the Coal Supply Agreement and Section 12 of the Amended and Restated Premises Lease Agreement during the term of this Agreement.

The parties each agree to indemnify the other as set forth in Section 12.11 of the Coal Supply Agreement, the terms of which are hereby incorporated into this Agreement. Nothing contained in this Agreement shall be construed to require either party to indemnify the other against the other party’s willful misconduct or negligence.

Virginia Power and Mettiki each shall comply with all federal, state and local laws, rules, regulations, orders and ordinances applicable to its performance hereunder. If fines, penalties or legal costs are assessed against a party by any government agency or court due to the other party’s noncompliance with such laws, rules, regulations or ordinances, the non-complying party shall indemnify and hold harmless the other party against any and all losses, liabilities, damages, claims and costs suffered or incurred because of the failure of the non-complying party to comply therewith. The non-complying party shall reimburse the other party for any and all legal or other expenses, including attorneys’ fees through the appellate level, reasonably incurred by the party in connection with such losses, liabilities, damages or claims.

-4-

a. The provisions of Section 12.1 of the Coal Supply Agreement shall apply to this Agreement with regard to assignment and the parties recognize that such assignment shall not alter the rights and obligations of the assigned party with respect to this Agreement and the Coal Supply Agreement.

b. Nothing herein shall be construed to restrict the right of Virginia Power to freely convey, assign, or otherwise dispose of or encumber its title, rights, and interests in the Premises. Any assignment made as provided herein shall not relieve Mettiki of any responsibility for the due and faithful performance hereof. Mettiki shall be liable for all acts and omissions of its assignee.

This Agreement is and shall be subject, subordinate to, and inferior to any lien or encumbrance now or hereafter placed on the Existing Trust Unloading Facility by Mettiki, all advances made under any such lien or encumbrance, the interest payable on any such lien or encumbrance, and any and all renewals or extensions of such liens or encumbrances.

Any notice required or permitted to be given in writing hereunder shall be executed in the manner set forth under Article 13 of the Coal Supply Agreement. The reference to “Seller” in such Article 13 shall mean “Mettiki” for purposes of this Agreement.

In the event that a governmental agency has authority to regulate the charges for, and conditions of, the leasing of the Existing Truck Unloading Facility as described in this Agreement, or acquires such authority subsequent to the effective date of this Agreement, then this Agreement shall be subject to regulation by such governmental agency (“Regulatory Change”). In such event, this Agreement shall be modified but only to the extent necessary to comply with such regulations. Any provisions of this Agreement not subject to regulation shall remain in full force and effect.

Both parties recognize that governmental or regulatory authorities having jurisdiction over Virginia Power or the activities contemplated by this Agreement may take action which prevents Virginia Power from performing its obligations under this Agreement. If any court, governmental or regulatory authority for any reason substantially prevents Virginia Power from performing its obligations under this Agreement, Virginia Power may, by written notice to Mettiki, immediately terminate this Agreement without obligation or liability to Mettiki, except for obligations and liabilities arising from any prior performance or breach of this Agreement. Such termination shall be effective upon the date specified in Virginia Power’s notice, but in no event earlier than Mettiki’s receipt of Virginia Power’s notice or if permitted by said court, governmental or regulatory

-5-

authority thirty (30) days after Mettiki’s receipt of Virginia Power’s notice. Termination of this Agreement as described in this Section shall not be cause for termination of the Coal Supply Agreement.

This Agreement and the rights of the parties hereunder shall be governed by, construed and enforced in accordance with the laws of the State of West Virginia. This Agreement shall be deemed to have been executed in West Virginia regardless of the actual place of signing or the actual place of performance.

The failure of either Mettiki or Virginia Power to demand strict performance of the terms of, or to exercise any right conferred in, this Agreement shall not be construed as a waiver or relinquishment of its right to assert or rely upon any such term or right in the future, or a consent to any continuing or subsequent failure or breach.

Section 12.4 of the Coal Supply Agreement is hereby incorporated into this Agreement.

This Agreement does not and shall not be construed to establish a partnership, joint venture or other form of business association between Mettiki and Virginia Power, and neither party shall have the authority to obligate the other without the other’s prior written consent. Virginia Power shall not be considered an employer, either individually or jointly with Mettiki, of any of Mettiki’s personnel or the personnel of Mettiki’s contractors, subcontractors or suppliers.

Article and paragraph headings contained herein are inserted for convenience and shall have no effect on interpretation or construction of this Agreement.

Subject to the provisions of subparagraph (h) above, no information relative to this Agreement shall be released by Mettiki for publication, advertising or for any other purpose without the prior written approval of Virginia Power.

Section 12.3 of the Coal Supply Agreement is hereby incorporated into this Agreement.

-6-

“Confidential Information” shall mean this Agreement or any part thereof and any information obtained as a result of negotiation and performance of this Agreement that either party identifies to the other as being confidential or proprietary in nature. Virginia Power and Mettiki agree to refrain from disclosing Confidential Information to any third party, except as may be required by a court, government agency or proper discovery request. If either party is so required to disclose Confidential Information, such party shall promptly notify the other party in advance of disclosure and shall use its best efforts to ensure that such disclosure is made on a confidential basis.

Notwithstanding the foregoing, state and federal regulatory agencies may require either party to this Agreement to routinely report to such agencies certain overall cost and physical property information related to this Agreement. A party may make such report as required without notice to the other party and without confidentiality restrictions, provided that such reporting does not substantially disclose the terms of this Agreement or the substance of other Confidential Information provided by the other party.

Nothing contained in subparagraph (g) above or this subparagraph (h) shall prohibit Mettiki’s parent entity, Alliance Resource Partners, L.P., from making any public disclosures regarding this Agreement and the transactions contemplated hereby if such disclosure is required by applicable securities laws or the rules of the Nasdaq National Market.

Each of the parties warrants and represents to the other that this Agreement and the transactions contemplated hereby have been duly authorized by all required corporate or limited liability company action, as the case may be.

Section 12.6 of the Coal Supply Agreement is hereby incorporated into this Agreement.

No amendment or modification of this Agreement shall be valid unless in writing and executed by the duly authorized representatives of both parties.

This Agreement and the provisions of the Coal Supply Agreement that are incorporated herein by reference embodies the entire agreement between the parties with respect to the subject matter hereof and supersedes any prior or contemporaneous agreement or understanding between the parties. The parties shall not be bound by or be liable for any statement, representation, promise, inducement or understanding of any kind or nature not set forth or provided for herein. No prior course of dealing, usage of trade or course of performance shall be used to supplement or explain any term, condition or instruction used in this Agreement, nor be deemed to effect any amendment.

-7-

Notwithstanding any other term or provision of this Agreement, in the event of a conflict between the terms and conditions of this Agreement, the Coal Supply Agreement and the provisions of any Annex or Attachment to the Coal Supply Agreement; the terms and conditions of the Coal Supply Agreement shall have precedence over the conflicting provisions of the Annex or Attachment, and this Agreement; and, the terms and conditions of the Annex or Attachment of the Coal Supply Agreement shall have precedence over the conflicting provisions of this Agreement. Except for the provisions of Section 5 of this Agreement, the parties acknowledge and agree that, notwithstanding any other term or provision of this Agreement, neither Virginia Power nor Mettiki will have any greater, reduced, additional or changed obligation, liability or duty to the other than as specified in the Coal Supply Agreement (including the Annexes and Attachments thereto).

IN WITNESS WHEREOF, the parties hereto have caused this Agreement to be executed by their respective officers thereunto duly authorized, on the date and year first above written.

-8-