Exhibit 10.1

Execution Version

AMENDED AND RESTATED

ADMINISTRATIVE SERVICES AGREEMENT

by and among

ALLIANCE RESOURCE PARTNERS, L.P.

ALLIANCE RESOURCE MANAGEMENT GP, LLC

ALLIANCE RESOURCE OPERATING PARTNERS, L.P.

ALLIANCE HOLDINGS GP, L.P.

ALLIANCE GP, LLC

and

ALLIANCE RESOURCE HOLDINGS II, INC.

(Effective January 1, 2010)

TABLE OF CONTENTS

ARTICLE 1: DEFINITIONS

i

AMENDED AND RESTATED

ADMINISTRATIVE SERVICES AGREEMENT

THIS AMENDED AND RESTATED ADMINISTRATIVE SERVICES AGREEMENT (this “Agreement”) is made effective the 1^st day of January 2010 (the “Effective Date”) by and among Alliance Resource Partners, L.P., a Delaware limited partnership (“ARLP”), Alliance Resource Management GP, LLC, a Delaware limited liability company and the managing general partner of ARLP (“MGP”), Alliance Resource Operating Partners, L.P., a Delaware limited partnership (“OLP”), Alliance Holdings GP, L.P., a Delaware limited partnership (“AHGP”), Alliance GP, LLC, a Delaware limited liability company and the general partner of AHGP (“AGP”), and Alliance Resource Holdings II, Inc. (“ARH II”).

R E C I T A L S

The Parties hereto desire, by their execution of this Agreement, to evidence the terms and conditions upon which ARLP will provide certain services to the AHGP Entities and the ARH II Entities. This Agreement supersedes in all respects the Administrative Services Agreement entered into by the Parties effective May 15, 2006.

A G R E E M E N T S

NOW, THEREFORE, in consideration of the premises and the covenants, conditions, and agreements contained herein, and for other good and valuable consideration, the receipt and sufficiency of which are hereby acknowledged, the Parties hereto hereby agree as follows:

ARTICLE 1: DEFINITIONS

1.1 Definitions. The definitions listed on Exhibit A shall be for all purposes, unless otherwise clearly indicated to the contrary, applied to the terms used in this Agreement.

1.2 Construction. Unless the context requires otherwise: (a) any pronoun used in this Agreement shall include the corresponding masculine, feminine or neuter forms, and the singular form of nouns, pronouns and verbs shall include the plural and vice versa; (b) references to Articles and Sections refer to Articles and Sections of this Agreement; (c) the terms “include”, “includes”, “including” or words of like import shall be deemed to be followed by the words “without limitation”; and (d) the terms “hereof”, “herein” or “hereunder” refer to this Agreement as a whole and not to any particular provision of this Agreement. The table of contents and headings contained in this Agreement are for reference purposes only, and shall not affect in any way the meaning or interpretation of this Agreement.

1

ARTICLE 2: SERVICES

2.1 Services. Beginning on the Effective Date, subject to the terms of this Article 2 and in exchange for the payment described in Section 2.3, ARLP hereby agrees to provide each of the AHGP Entities and the ARH II Entities with such general administrative and management services, including but not limited to human resources, information technology, financial and accounting services, legal services and other services (the “Services”) as may be necessary to manage the business of the AHGP Entities and the ARH II Entities, as applicable, in accordance with the Services Standard; it being understood and agreed by the Parties that in connection with the provision of such Services, ARLP shall employ or otherwise retain such personnel as may be necessary to provide the Services. The names of such personnel are set forth on Annex A hereto and will be updated on or about December 1 of each year in accordance with the procedures set forth in Section 2.5.

2.2 Provision of Insurance. ARLP hereby agrees to cause each of the ARLP Entities, the AHGP Entities and the ARH II Entities to be named as additional insureds in ARLP’s insurance program, as in effect from time to time. Each of the ARLP Entities, the AHGP Entities and the ARH II Entities, as applicable, shall be allocated, and pay for, such insurance coverage in an amount equal to ARLP’s cost of insuring the assets and operations of such partnership entities.

2.3 Payment for Services. (a) As remuneration for the provision to each of the AHGP Entities and the ARH II Entities of the Services, ARLP shall be entitled to receive, and the AHGP Entities and the ARH II Entities, as applicable, agree to pay to ARLP, an amount equal to the percentage of each employee’s compensation allocable to each of the AHGP Entities and the ARH II Entities as the same are set forth on Annex A hereto. In addition, each of the AHGP Entities and the ARH II Entities shall pay all sales, use, excise, value added or similar taxes, if any, that may be applicable from time to time in respect of the Services provided to such entities by ARLP. The aggregate amount payable by the AHGP Entities or the ARH II Entities to ARLP pursuant to this Section 2.3(a) with respect to a given period of time shall be referred to herein as the “Administrative Services Fee.” It is the intention of the Parties that the Administrative Services Fee represents fair and reasonable compensation to ARLP for the AHGP Entities’ or the ARH II Entities’, as applicable, allocable share of the base salaries, employer costs for employee benefits, bonuses paid and provided to such personnel by ARLP, or any of its Affiliates. The amount of the Administrative Services Fee shall not be adjusted except in accordance with Section 2.5, notwithstanding any change in personnel or the Services provided to any of the AHGP Entities or the ARH II Entities, respectively.

(b) In addition, the AHGP Entities and ARH II Entities shall pay ARLP an aggregate annual amount of $75,000 ($18,750 per quarter) for certain shared fixed costs including, but not limited to, office lease, telephone and office equipment leases (the “Fixed Charges Fee”). It is the intention of the Parties that the Fixed Charges Fee represents fair and reasonable remuneration to ARLP for the AHGP Entities’ and the ARH II Entities’ use of the facilities and equipment of ARLP and its Affiliates. The AHGP Entities and the ARH II Entities shall each pay to ARLP their respective pro rata portion of the Fixed Charges Fee based on the relative allocation of employee compensation as set forth on Annex A hereto to the AHGP Entities, on one hand and the ARH II Entities on the other hand. The amount of the Fixed Charges Fee shall not be adjusted except in accordance with Section 2.5.

2

2.4 Invoices. ARLP shall invoice the applicable Billing Agent on or before ten days following the end of each fiscal quarter for the Administrative Services Fee and the Fixed Charges Fee for such quarter. All invoices shall be due and payable on the 45th day following the end of each fiscal quarter.

2.5 Annual Reallocation. On or about December 1 of each year, ARLP or its Affiliate shall submit for approval a revised Annex A (the “Proposed Annex A”) and a new estimate of the Fixed Charges Fee (the “Proposed Fixed Charges Fee”) to the board of directors of each of MGP, AGP and ARH II. The Proposed Annex A will reflect any changes in personnel of ARLP or its Affiliates who are performing the Services, changes in each such employee’s compensation and ARLP’s good faith estimate of the time each such employee will spend performing Services on behalf of each of the AHGP Entities and the ARH II Entities, respectively, taking into account prior performance and future expectations; provided, however, with respect to Services performed on behalf of the ARH II Entities, no time shall be allocated for an employee performing such Services unless having such employee available to perform such Services results in an incremental cost to ARLP. The Proposed Fixed Charges Fee shall reflect ARLP’s good faith estimate of the amount of fixed costs allocable to the AHGP Entities and the ARH II Entities. Once approved by the board of directors of each of MGP, AGP and ARH II, or pursuant to the provisions of Section 2.6, the Proposed Annex A and the Proposed Fixed Charges Fee shall become part of this Agreement and replace the existing Annex A and the Fixed Charges Fee until such time as a new Proposed Annex A and the Proposed Fixed Charges Fee is approved in accordance with the provisions of this Section 2.5 or Section 2.6.

In addition, ARLP or its Affiliate shall prepare a schedule detailing the variance between the estimated allocation of time spent by its personnel on behalf of each of the AHGP Entities and the ARH II Entities in the past fiscal year (the “Adjusted Administrative Services Fee”) and submit such schedule for approval to the board of directors of each of MGP, AGP and ARH II. Upon approval by the board of directors of each of MGP, AGP and ARH II, or pursuant to the provisions of Section 2.6, the difference between the Administrative Services Fee paid and the Adjusted Administrative Services Fee shall be paid by or reimbursed to each Entity within 60 days of the fiscal year end.

2.6 Disputes. Should there be a dispute over the nature or quality of the Services, the calculation and allocation of the Administrative Services Fee in connection with a Proposed Annex A the allocation of fixed charge in connection with the Fixed Charges Fee or the Adjusted Administrative Services Fee, ARLP and the applicable Entities shall first attempt to resolve such dispute, acting diligently and in good faith, using the past practices of such Parties and documentary evidence of costs as guidelines for such resolution. If ARLP and the applicable Entities are unable to resolve any such dispute within thirty days, or such additional time as may be reasonable under the circumstances, the dispute shall be referred to the applicable Conflicts Committees (or in the case of ARH II, to its board of directors) for resolution. The Parties agree that the applicable Conflicts Committees and the board of directors of ARH II shall have the authority to settle any such dispute, in their sole discretion, recognizing that it is the intent of all Parties that all shared expenses, services and the fixed costs, as applicable, be allocated among

3

the ARLP Entities, the AHGP Entities or the ARH II Entities, as applicable, on a fair and reasonable basis. If, following good faith negotiation, the applicable Conflicts Committee and/or the board of directors of ARH II cannot resolve any dispute, ARLP shall have the right, but not the obligation, to withhold the provision of any Services until such time as the Entities resolve the dispute.

2.7 Representations Regarding Use of Services. Each of the AHGP Entities and the ARH II Entities represent and agree that it will use the Services only in accordance with all applicable federal, state and local laws and regulations, and in accordance with the reasonable conditions, rules, regulations, and specifications that may be set forth in any manuals, materials, documents, or instructions furnished from time to time by ARLP or its Affiliate to such entities. ARLP reserves the right to take all actions, including, without limitation, termination of any portion of the Services, that it reasonably believes is required to assure compliance with applicable laws and regulations.

2.8 Warranties; Limitation of Liability. The Services shall be provided in accordance with the Services Standard. EXCEPT AS SET FORTH IN THE PRECEDING SENTENCE, ARLP MAKES NO (AND HEREBY DISCLAIMS AND NEGATES ANY AND ALL) WARRANTIES OR REPRESENTATIONS WHATSOEVER, EXPRESS OR IMPLIED, WITH RESPECT TO THE SERVICES. IN NO EVENT SHALL ARLP OR ANY OF ITS AFFILIATES BE LIABLE TO ANY OF THE PERSONS RECEIVING ANY SERVICES OR TO ANY OTHER PERSON FOR ANY EXEMPLARY, PUNITIVE, INDIRECT, INCIDENTAL, CONSEQUENTIAL, OR SPECIAL DAMAGES RESULTING FROM ANY ERROR IN THE PERFORMANCE OF SUCH SERVICE, REGARDLESS OF WHETHER THE PERSON PROVIDING SUCH SERVICE, ITS AFFILIATES, OR OTHERS MAY BE WHOLLY, CONCURRENTLY, PARTIALLY, OR SOLELY NEGLIGENT OR OTHERWISE AT FAULT, EXCEPT TO THE EXTENT SUCH EXEMPLARY, PUNITIVE, INDIRECT, INCIDENTAL, CONSEQUENTIAL OR SPECIAL DAMAGES ARE PAID BY THE PARTY INCURRING SUCH DAMAGES TO A THIRD PARTY.

2.9 Force Majeure. ARLP shall have no obligation to perform the Services if its failure to do so is caused by or results from any act of God, governmental action, natural disaster, strike, failure of essential equipment, or any other cause or circumstance, whether similar or dissimilar to the foregoing causes or circumstances, beyond the reasonable control of ARLP.

2.10 Affiliates. At its election, ARLP may cause one or more of its Affiliates or third party contractors reasonably acceptable to the Party receiving any Services to provide such Services; provided, however, ARLP shall remain responsible for the provision of such Services in accordance with this Agreement.

ARTICLE 3: OTHER AGREEMENTS

3.1 Adoption of Policies and Procedures. The Boards of Directors of MGP, AGP and ARH II have adopted the policies and procedures attached hereto as Exhibit B to govern their relationship with respect to this Agreement.

4

ARTICLE 4: MISCELLANEOUS

4.1 Choice of Law; Submission to Jurisdiction. This Agreement shall be subject to and governed by the laws of the State of Delaware.

4.2 Termination. Any party hereto may terminate this Agreement by providing written notice to the other Parties of its intention to terminate this Agreement, which notice must be provided at least 90 days prior to such termination. ARLP may terminate this Agreement by providing 30 days’ prior written notice to any of the AHGP Entities and the ARH II Entities at any time during which a Payment Default has occurred and is continuing for a period of more than 30 days.

4.3 Notices. All notices or requests or consents provided for or permitted to be given pursuant to this Agreement must be in writing and must be given by depositing same in the United States mail, addressed to the Party to be notified, postpaid, and registered or certified with return receipt requested or by delivering such notice in person, by facsimile or electronic mail to such Party. Notice given by personal delivery or mail shall be effective upon actual receipt. Notice given by facsimile or by electronic mail shall be effective upon actual receipt if received during the recipient’s normal business hours, or at the beginning of the recipient’s next business day after receipt if not received during the recipient’s normal business hours. All notices to be sent to a Party pursuant to this Agreement shall be sent to or made at the address set forth below such Party’s signature to this Agreement, or at such other address as such Party may stipulate to the other Parties in the manner provided in this Section 4.3.

4.4 Entire Agreement; Supersedure. This Agreement constitutes the entire agreement of the Parties relating to the matters contained herein, superseding all prior contracts or agreements, whether oral or written, relating to the matters contained herein.

4.5 Effect of Waiver of Consent. No Party’s express or implied waiver of, or consent to, any breach or default by any Party in the performance by such Party of its obligations hereunder shall be deemed or construed to be a consent or waiver to or of any other breach or default in the performance by such Party of the same or any other obligations of such Party hereunder. Failure on the part of a Party to complain of any act of any Party or to declare any Party in default, irrespective of how long such failure continues, shall not constitute a waiver by such Party of its rights hereunder until the applicable statute of limitations period has run.

4.6 Amendment or Modification. This Agreement may be amended or modified from time to time only by the agreement of all the Parties affected by any such amendment; provided, however, that ARLP and AHGP may not, without the prior approval of its respective Conflicts Committee, agree to any amendment or modification of this Agreement that, in the reasonable discretion of the MGP or AGP, as applicable, will materially and adversely affect the holders of units of ARLP or AHGP, as applicable.

4.7 Assignment. No Party shall have the right to assign its rights or obligations under this Agreement without the consent of the other Parties.

5

4.8 Counterparts. This Agreement may be executed in any number of counterparts with the same effect as if all Parties had signed the same document. All counterparts shall be construed together and shall constitute one and the same instrument.

4.9 Severability. If any provision of this Agreement or the application thereof to any Party or circumstance shall be held invalid or unenforceable to any extent, the remainder of this Agreement and the application of such provision to other Parties or circumstances shall not be affected thereby and shall be enforced to the greatest extent permitted by law.

4.10 Further Assurances. In connection with this Agreement and all transactions contemplated by this Agreement, each Party hereto agrees to execute and deliver such additional documents and instruments and to perform such additional acts as may be necessary or appropriate to effectuate, carry out and perform all of the terms, provisions and conditions of this Agreement and all such transactions.

4.11 Withholding or Granting of Consent. Unless the consent or approval of a Party is expressly required not to be unreasonably withheld (or words to similar effect), each Party may, with respect to any consent or approval that it is entitled to grant pursuant to this Agreement, grant or withhold such consent or approval in its sole and uncontrolled discretion, with or without cause, and subject to such conditions as it shall deem appropriate.

4.12 U.S. Currency. All sums and amounts payable or to be payable pursuant to the provisions of this Agreement shall be payable in coin or currency of the United States of America that, at the time of payment, is legal tender for the payment of public and private debts in the United States of America.

4.13 Laws and Regulations. Notwithstanding any provision of this Agreement to the contrary, no Party hereto shall be required to take any act, or fail to take any act, under this Agreement if the effect thereof would be to cause such Party to be in violation of any applicable law, statute, rule or regulation.

4.14 Negation of Rights of Third Parties. The provisions of this Agreement are enforceable solely by the Parties, and no Limited Partner or other Person shall have the right to enforce any provision of this Agreement or to compel any Party to comply with the terms of this Agreement.

6

IN WITNESS WHEREOF, the Parties have caused this Agreement to be duly executed by their respective authorized officers as of January 1, 2010.

Signature Page to Administrative Services Agreement

Signature Page to Administrative Services Agreement

Exhibit A

DEFINED TERMS

“Adjusted Administrative Services Fee” shall have the meaning set forth in Section 2.5.

“Administrative Services Fee” shall have the meaning set forth in Section 2.3(a).

“Affiliate” shall mean, with respect to any Person, any other Person that directly or indirectly through one or more intermediaries controls, is controlled by or is under common control with, the Person in question. As used herein, the term “control” means the possession, direct or indirect, of the power to direct or cause the direction of the management and policies of a Person, whether through ownership of voting securities, by contract or otherwise. Notwithstanding the foregoing, a Person shall only be considered an “Affiliate” of the general partner of ARLP or AHGP, as applicable, if such Person owns, directly or indirectly, 50% or more of the voting securities of such general partner or otherwise possesses the sole power to direct or cause the direction of the management and policies of such general partner; provided however, that for purposes of this Agreement none of the ARLP Entities, or the ARH II Entities, as applicable, shall be deemed to be Affiliates of AGP.

“Agreement” shall mean this Administrative Services Agreement, as it may be amended, modified, or supplemented from time to time.

“Billing Agent” shall mean ARH II, and in the case of ARLP, MGP, and in the case of AHGP, AGP.

“AHGP” shall have the meaning set forth in the introductory paragraph of this Agreement.

“AHGP Entities” shall mean AHGP and AGP and any Affiliate controlled (and only so long as such Affiliates are controlled) by AHGP or AGP (as the term “control” is used in the definition of “Affiliate”) but excluding the ARLP Entities.

“AGP” shall have the meaning set forth in the introductory paragraph of this Agreement.

“ARH II” shall have the meaning set forth in the introductory paragraph of this Agreement.

“ARH II Entities” shall mean ARH II and any Affiliate controlled (and only so long as such Affiliates are controlled) by ARH II (as the term “control” is used in the definition of “Affiliate”) but excluding the ARLP Entities and the AHGP Entities.

“ARLP” shall have the meaning set forth in the introductory paragraph of this Agreement.

“ARLP Entities” shall mean ARLP, MGP, OLP, Alliance Resource GP, LLC and any Affiliate controlled (and only so long as such Affiliates are controlled) by ARLP, MGP, OLP, Alliance Resource GP, LLC (as the term “control” is used in the definition of “Affiliate”).

A-1

“Conflicts Committee” when used in reference to ARLP or an ARLP Entity, shall have the meaning set forth in the partnership agreement of ARLP and when used in reference to AHGP or an AHGP Entity, shall have the meaning set forth in the partnership agreement of AHGP.

“Effective Date” shall have the meaning set forth in the introductory paragraph of this Agreement.

“Entities” shall mean the ARLP Entities, the AHGP Entities and the ARH II Entities.

“Fixed Charges Fee” shall have the meaning set forth in Section 2.3(b).

“MGP” shall have the meaning set forth in the introductory paragraph of this Agreement.

“OLP” shall have the meaning set forth in the introductory paragraph of this Agreement.

“Party” shall mean any one of the Persons that executes this Agreement.

“Payment Default” shall mean the failure of an Entity to pay the invoices described in Section 2.4 on or before the 45th day following the end of each fiscal quarter

“Person” means an individual or a corporation, limited liability company, partnership, joint venture, trust, unincorporated organization, association, government agency or political subdivision thereof or other entity.

“Proposed Annex A” shall have the meaning set forth in Section 2.5.

“Proposed Fixed Charges Fee” shall have the meaning set forth in Section 2.5.

“Services” shall have the meaning set forth in Section 2.1.

“Services Standard” shall mean, with respect to the performance of the Services, the good faith undertaking, on a commercially reasonable basis, to perform the Services in all material respects in compliance with applicable laws and prudent industry practices.

A-2

Exhibit B

CONFLICTS POLICIES AND PROCEDURES

Capitalized terms used but not defined in this Exhibit B shall have the meanings assigned to such terms in that certain Administrative Services Agreement, effective February     , 2010, of which this Exhibit B forms a part.

This Exhibit B outlines the corporate governance structure and the policies and procedures that have been adopted by the boards of directors of AGP, MGP and ARH II to address potential conflicts among, protect the confidential information of, and govern the sharing of ARLP personnel among, the Entities.

Shared Services

Employees of ARLP or its Affiliates may be assigned to perform Shared Services for all or any of the AHGP Entities and the ARH II Entities. Employees of ARLP or its Affiliates performing Shared Services may be appointed to officer positions (including executive officer positions) at each of MGP, AGP and ARH II or their respective controlled Affiliates. As a result of their performance of Shared Services, Shared Employees may obtain Commercial Information that relates to more than one of the groups of Entities. To the extent that any Shared Employee has Commercial Information that relates to any two or more of the ARLP Entities, the AHGP Entities and the ARH II Entities, such Shared Employee shall not engage in any activities to which such Commercial Information relates unless such activities are approved by the Screening Officer of each respective Entity.

Information Screening for Shared Employees

To the fullest extent possible, Shared Employees should avoid access to Commercial Information for any Entities for which they do not perform Commercial and Development Activities. To the extent that any Shared Employee who engages in Commercial and Development Activities becomes privy to Commercial Information of any Entities for which such employee does not perform Commercial and Development Activities, such Shared Employee must report that fact and the nature of the Confidential Information to the Screening Officers who will maintain a record of the name of the person, the date of the report, and the nature of the Commercial Information obtained by the Shared Employee.

Except as expressly permitted by the Screening Officers and to the extent required to effectively perform the Shared Services, (i) Shared Employees shall not disclose Commercial Information of the ARLP Entities to any director, officer or employee associated with the AHGP Entities or ARH II Entities; (ii) Shared Employees shall not disclose Commercial Information of the AHGP Entities to any director, officer or employee associated with the ARLP Entities or ARH II Entities and (iii) Shared Employees shall not disclose Commercial Information of the ARH II Entities to any director, officer or employee associated with the ARLP Entities or AHGP Entities.

Shared Employees should seek guidance on the foregoing restrictions from the Screening Officers to the extent that they are uncertain as to an appropriate course of action.

B-1

Definitions

For purposes of these policies and procedures, capitalized terms used but not defined above shall have the following meanings:

“Commercial and Development Activities” shall mean operations of the Entities relating to sales, marketing, or other services provided to customers; operation of or proposed changes to, such Entities’ assets; and the plans and strategies dealing with the business of such Entities.

“Commercial Information” shall mean information about Commercial and Development Activities or other competitively sensitive information of any Entities. Commercial Information includes information regarding prices, costs, margins, volumes and contractual terms for any particular customer; any method, tool or computer program used to determine prices for any asset; all plans or strategies used or adopted to negotiate, target or identify a particular customer for any asset; all information regarding plans and prospective budgets to expand or build a new facility; all information regarding a proposal to buy an existing facility; and capacity and capacity utilization of any facility.

“Independent Director” shall mean an individual director who meets the independence, qualification and experience requirements established by the Securities Exchange Act of 1934, as amended, and the rules and regulations of the Securities and Exchange Commission thereunder and by the Nasdaq National Market.

“Screening Officer” shall mean the chief legal officer or general counsel for each of ARH II, AGP and MGP.

“Shared Employees” shall mean employees of ARLP or its Affiliates providing Shared Services.

“Shared Services” shall mean services provided by employees of ARLP or its Affiliates to more than one of the groups of Entities comprising the ARLP Entities, the AHGP Entities and the ARH II Entities and such services shall include, but not be limited to, human resources, information technology, financial and accounting services, legal services and such other services that do not involve Commercial and Development Activities.

B-2

ANNEX A

PERSONNEL ALLOCATION