Exhibit 5.1

February 17, 2023

AutoNation, Inc.

200 SW 1st Ave, Ste 1600

Fort Lauderdale, FL 33301

RE: AutoNation, Inc.

Registration Statement on Form S-8

Ladies and Gentlemen:

I am Executive Vice President, General Counsel and Corporate Secretary of AutoNation, Inc., a Delaware corporation (the “Company”), and have acted as counsel in connection with the registration under the Securities Act of 1933, as amended (the “Securities Act”), of $100,000,000 of the Company’s deferred compensation obligations (the “Obligations”), which represent general unsecured obligations of the Company to pay deferred compensation in the future in accordance with the terms of the AutoNation, Inc. Deferred Compensation Plan, amended and restated, effective January 1, 2022 (the “Plan”). Such registration is pursuant to the Registration Statement on Form S-8 (the “Registration Statement”) being filed by the Company with the U.S. Securities and Exchange Commission on February 17, 2023.

I have examined originals or copies, certified or otherwise identified to my satisfaction, of such corporate documents and records which I have deemed necessary or appropriate for the purposes of the opinion and have conducted such other investigations of fact and law as I have deemed necessary or advisable for purposes of this opinion. I have also made such inquiries of such officers and representatives as I have deemed relevant and necessary as a basis for the opinions hereafter set forth. In such examination, I have assumed, without independent investigation, the genuineness of all signatures, the legal capacity of all individuals who have executed any of the documents, the authenticity of all documents submitted to me as originals and the conformity to original documents of documents submitted to me as certified or photostatic copies.

Based upon the foregoing, I am of the opinion that:

1. The Obligations, when incurred in accordance with the terms of the Plan, will be valid and binding obligations of the Company, enforceable against the Company in accordance with the terms of the Plan, except as enforcement thereof may be limited by bankruptcy, insolvency or other laws of general applicability relating to or affecting creditors’ rights or by general equity principles; and

2. The provisions of the written document constituting the Plan are in compliance with the requirements of the Employee Retirement Income Security Act of 1974, as amended, pertaining to such provisions.

I hereby consent to the filing of the opinion as an exhibit to the Registration Statement. In giving such consent, I do not admit that I am in the category of persons whose consent is required under Section 7 of the Securities Act.

Very truly yours,

/s/ C. Coleman Edmunds

C. Coleman Edmunds

Executive Vice President, General Counsel and Corporate Secretary