Exhibit 5.1

[Arch Coal, Inc. letterhead]

January 6, 2009

Board of Directors
Arch Coal, Inc.
One CityPlace Drive, Suite 300
St. Louis, Missouri 63141

Dear Ladies and Gentlemen:

     I am Assistant General Counsel and Assistant Secretary for Arch Coal, Inc., a Delaware corporation (the “Company”). This opinion letter is being furnished to you in connection with the registration under the Securities Act of 1933, as amended (the “Act”), of up to 1,000,000 shares of the Company’s common stock, par value $0.01 per share (the “Shares”) which may be offered and sold under the Arch Coal, Inc. and Subsidiaries Employee Thrift Plan (the “Plan”).

     In connection herewith, I have examined the Registration Statement on Form S-8 (Reg. No. 333-          ) (the “Registration Statement”) to be filed with the Securities and Exchange Commission under the Act. I have also examined originals or copies certified or otherwise identified to my satisfaction of such other corporate records, agreements and instruments of the Company, certificates of public officials and officers of the Company and such other documents, records and instruments, and I have made such legal and factual inquiries as I have deemed necessary or appropriate as a basis to render the opinion hereinafter expressed.

     In my examination of the foregoing, I have assumed the genuineness of all signatures on all documents examined by me (except the signatures of officers of the Company), the legal competence and capacity of each person executing documents, the authenticity of all documents submitted to me as originals, the conformity to authentic originals of all documents submitted to me as certified or photostatted copies, and the due authorization, execution and delivery of all documents (other than due authorization, execution and delivery on behalf of the Company) where due authorization, execution and delivery are a prerequisite to the effectiveness thereof.

     Based upon the foregoing and in reliance thereon, and subject to the exceptions, qualifications and limitations stated herein, I am of the opinion that:

     1. The Company is a corporation duly incorporated, validly existing and in good standing under the laws of the State of Delaware.

     2. The Shares have been duly authorized and, when offered and sold by the Company pursuant to the Plan, will be legally issued, fully paid and nonassessable.

     The opinion expressed above is limited to the laws of the State of Missouri, the Federal laws of the United States of America and, to the extent required by the foregoing, the General Corporation Law of the State of Delaware as in effect (and published or otherwise generally available) on the date hereof, and I assume no obligation to revise or supplement the opinion should such law be changed by legislative action, judicial decision or otherwise. In rendering the opinion, I have not considered, and hereby disclaim any opinion as to, the application or impact of any laws, cases, decisions, rules or regulations of any other jurisdiction, court or administrative agency.

     I hereby consent to the filing of this opinion letter as Exhibit 5.1 to the Registration Statement. In giving such consent, I do not thereby concede that I am within the category of persons whose consent is required under Section 7 of the Act or the rules and regulations of the Commission thereunder.

Sincerely,

/s/ Gregory A. Billhartz

Gregory A. Billhartz
Assistant General Counsel and Assistant Secretary