Exhibit 5.1

                King & Spalding LLP                 1180 Peachtree Street N.E.                 Atlanta, GA 30309-3521                 www.kslaw.com

March 13, 2012

FleetCor Technologies, Inc.

5445 Triangle Parkway

Suite 400

Norcross, Georgia 30092-2575

Re: Registration Statement on Form S-3

Ladies and Gentlemen:

We have acted as counsel to FleetCor Technologies, Inc., a Delaware corporation (the “Company”), in connection with the offering and sale from time to time, on a delayed or continuous basis, by certain stockholders of the Company of the Company’s common stock, par value $0.001 per share (the “Secondary Shares”), as contemplated by the Company’s registration statement on Form S-3 to which this opinion has been filed as an exhibit (the “Registration Statement”). The Secondary Shares may be offered and sold from time to time pursuant to Rule 415 under the Securities Act of 1933, as amended.

In connection with this opinion, we have examined and relied upon such records, documents, certificates and other instruments as in our judgment are necessary or appropriate to form the basis for the opinions hereinafter set forth.

In all such examinations, we have assumed the genuineness of signatures on all documents submitted to us as originals and the conformity to original documents of all copies submitted to us as certified, conformed or photographic copies, and as to certificates of public officials, we have assumed the same to have been properly given and to be accurate. As to matters of fact material to this opinion, we have relied, without independent verification, upon statements and representations of representatives of the Company and public officials.

This opinion is limited in all respects to the corporate laws of the State of Delaware (which includes the Delaware General Corporation Law, applicable provisions of the Delaware Constitution and reported judicial interpretations concerning those laws), and no opinion is expressed with respect to the laws of any other jurisdiction or any effect which such laws may have on the opinions expressed herein. This opinion is limited to the matters stated herein, and no opinion is implied or may be inferred beyond the matters expressly stated herein.

FleetCor Technologies, Inc.

March 13, 2012

Page 2

Based upon the foregoing, and subject to all of the assumptions, limitations and qualifications set forth herein, we are of the opinion that the Secondary Shares have been duly authorized and are validly issued, fully paid and nonassessable.

This opinion is given as of the date hereof, and we assume no obligation to advise you after the date hereof of facts or circumstances that come to our attention or changes in law that occur which could affect the opinions contained herein. This opinion is being rendered for the benefit of the Company in connection with the matters addressed herein.

We consent to the filing of this opinion as an Exhibit to the Registration Statement and to the reference to us under the caption “Legal Matters” in the Registration Statement.

Very truly yours,

/s/ King & Spalding LLP

King & Spalding LLP