Exhibit 3.1

AMENDED AND RESTATED

CERTIFICATE OF INCORPORATION

OF

FLEETCOR TECHNOLOGIES, INC.

(Originally Incorporated on February 3, 1998)

FIRST. The name of the corporation is FleetCor Technologies, Inc. (the “Corporation”).

SECOND. The address of its registered office in the State of Delaware is 1209 Orange Street, in the City of Wilmington, County of New Castle, Delaware 19801. The name of its registered agent at such address is The Corporation Trust Company.

THIRD. The nature of the business of the Corporation is to engage in any lawful act or activity for which a corporation may be organized under the Delaware General Corporation Law (the “DGCL”) and to possess and exercise all of the powers and privileges granted under such law and the other laws of the State of Delaware.

FOURTH. The total number of shares of all classes of capital stock which the Corporation shall have authority to issue is 500,000,000 consisting of 475,000,000 shares of common stock with a par value of $0.001 per share (hereinafter referred to as the “Common Stock”) and 25,000,000 shares of preferred stock with a par value of $0.001 per share (hereinafter referred to as the “Preferred Stock”).

The following is a statement of the designations and the powers, privileges and rights, and the qualifications, limitations or restrictions thereof in respect of each class of capital stock of the Corporation.

1. General. All shares of Common Stock will be identical and will entitle the holders thereof to the same rights, powers and privileges. The Common Stock shall be subject to all of the rights, privileges, preferences and priorities of the Preferred Stock as set forth in any certificates of designations filed to establish any series of Preferred Stock.

2. Dividends. Dividends may be declared and paid on the Common Stock from funds lawfully available therefor as and when determined by the Board of Directors of the Corporation (the “Board of Directors”) and subject to any preferential dividend rights of any then outstanding Preferred Stock.

3. Dissolution, Liquidation or Winding Up. In the event of any dissolution, liquidation, or winding up of the Corporation, whether voluntary or involuntary, the holders of the Common Stock, and holders of any class or series of

stock entitled to participate therewith, in whole or in part, as to the distribution of assets in such event, shall become entitled to participate in the distribution of any assets of the Corporation remaining after the Corporation shall have paid, or provided for payment of, all debts and liabilities of the Corporation and after the Corporation shall have paid, or set aside for payment, to the holders of any class or series of stock having preference over the Common Stock in the event of dissolution, liquidation or winding up the full preferential amounts (if any) to which they are entitled.

4. Voting Rights. Except as otherwise required by law or this Amended and Restated Certificate of Incorporation, each holder of Common Stock shall have one vote in respect of each share of Common Stock held of record by such holder on the books of the Corporation for the election of directors and on all matters submitted to a vote of stockholders of the Corporation; provided, however, that, except as otherwise required by law, holders of Common Stock shall not be entitled to vote on any amendment to this Certificate of Incorporation (including any Preferred Stock Designation relating to any series of Preferred Stock) that relates solely to the terms of one or more outstanding series of Preferred Stock if the holders of such affected series are entitled, either separately or together as a class with the holders of one or more other such series, to vote thereon pursuant to this Certificate of Incorporation (including any Preferred Stock Designation relating to any series of Preferred Stock). Except as otherwise required by law or provided herein, holders of Common Stock and any holders of Preferred Stock who are entitled to vote generally with the holders Common Stock, shall vote together as a single class, subject to any special or preferential voting rights of any then outstanding Preferred Stock. There shall be no cumulative voting.

The Preferred Stock may be issued from time to time in one or more series. The Board of Directors is hereby authorized to provide by resolution for the issuance of shares of Preferred Stock in one or more series and, by filing a certificate pursuant to the applicable law of the State of Delaware (hereinafter referred to as “Preferred Stock Designation”), setting forth such resolution, to establish by resolution from time to time the number of shares to be included in each such series, and to fix by resolution the designation, powers, preferences and relative, participating, optional or other rights, if any, of the shares of each such series and the qualifications, limitations and restrictions thereof. The number of authorized shares of Preferred Stock may be increased or decreased (but not below the number of shares thereof outstanding) by the affirmative vote of the holders of a majority of the voting power of all the then-outstanding shares of capital stock of the Corporation entitled to vote thereon, without a vote of the holders of the Preferred Stock, or any series thereof, unless a vote of any such holders is required pursuant to the terms of any Preferred Stock designation.

The authority of the Board of Directors with respect to each series shall include, but not be limited to, determination of the following:

2

FIFTH. The Corporation is to have perpetual existence.

SIXTH.

1. Management of Business and Affairs of the Corporation. The business and affairs of the Corporation shall be managed by, or under the direction of, the Board of Directors. In addition to the powers and authority expressly conferred upon them by statute or by this Amended and Restated Certificate of Incorporation or the Corporation’s Amended and Restated Bylaws, as amended and in effect from time to time (the “Bylaws”), the directors are hereby empowered to exercise all such powers and do all such acts and things as may be exercised or done by the Corporation.

2. Number of Directors. Subject to the rights of the holders of any series of Preferred Stock to elect additional directors under specified circumstances, the number of directors of the Corporation shall be such number as from time to time shall be fixed by, or in the manner provided in, the Bylaws of the Corporation, but in no event shall the number of directors be less than three. Directors need not be stockholders of the Corporation.

3

3. Classes of Directors. The Board of Directors, other than those directors who may be elected by the holders of any series of Preferred Stock under specified circumstances, shall consist of three classes (Class I, Class II and Class III).

4. Election of Directors. Elections of directors need not be by written ballot except as and to the extent provided in the Bylaws of the Corporation.

5. Terms of Office. Pursuant to Section 3 of this Article Sixth, Class I directors shall initially serve until the annual meeting of stockholders to be held in 2011; Class II directors shall initially serve until the annual meeting of stockholders to be held in 2012; and Class III directors shall initially serve until the annual meeting of stockholders to be held in 2013. At the time the classification of the Board of Directors into three classes becomes effective, the Board of Directors may assign the directors already in office to such classes. At each annual meeting of stockholders, directors elected to succeed those directors whose terms expire at that meeting shall be elected for a term of office to expire at the third succeeding annual meeting of stockholders after their election. A director shall hold office until the annual meeting of stockholders for the year in which such director’s term expires and until his or her successor shall be elected and qualified, subject, however to prior death, resignation, retirement, disqualification or removal from office. No decrease in the number of directors constituting the whole Board of Directors shall shorten the term of an incumbent director.

6. Allocation of Directors Among Classes in the Event of Increases or Decreases in the Number of Directors. In the event of any increase or decrease in the authorized number of directors (i) each director then serving as such shall nevertheless continue as director of the class of which he or she is a member until the expiration of such director’s current term or his or her prior death, resignation or removal and (ii) the newly created or eliminated directorships resulting from such increase or decrease shall be apportioned by the Board of Directors among the three classes of directors so as to ensure that no one class has more than one director more than any other class. To the extent possible, consistent with the foregoing rule, any newly created directorships shall be added to those classes whose terms of office are to expire at the latest dates following such allocation, and any newly eliminated directorships shall be subtracted from those classes whose terms of offices are to expire at the earliest dates following such allocation, unless otherwise provided for from time to time by resolution adopted by a majority of the directors then in office, though less than a quorum.

7. Vacancies. Subject to the rights of holders of any class or series of Preferred Stock then outstanding to elect directors under specified circumstances, any vacancy in the Board of Directors and any newly-created directorship, however occurring, including a newly-created directorship resulting from an enlargement of the Board of Directors, shall, unless otherwise required by law or by resolution of the Board of Directors, be filled only by vote of a majority of the directors then in office, even if less than a quorum, or by a sole remaining director (and not by stockholders). A director elected to fill a vacancy shall be elected for the unexpired term of his or her predecessor in office, if applicable. A director chosen to fill a position resulting from an increase in the number of directors shall hold office until the next election of the

4

class for which such director shall have been chosen and until his or her successor is elected and qualified, or until his or her earlier death, resignation or removal.

8. Removal. Subject to the rights of holders of any class or series of Preferred Stock then outstanding, any director, or the entire Board of Directors, may be removed from office, but only for cause and only by the affirmative vote of at least sixty-six and two-thirds percent (66 2/3%) of the voting power of all of the then outstanding shares of the capital stock of the Corporation entitled to vote generally in the election of directors, voting together as a single class.

9. Stockholder Nominations and Introduction of Business, Etc. Advance notice of stockholder nominations for election of directors and other business to be brought by stockholders before a meeting of stockholders shall be given in the manner provided in the Bylaws of the Corporation.

SEVENTH. A director of the Corporation shall not be personally liable to the Corporation or its stockholders for monetary damages for breach of fiduciary duty as a director, except for liability (i) for any breach of the director’s duty of loyalty to the Corporation or its stockholders, (ii) for acts or omissions not in good faith or which involve intentional misconduct or a knowing violation of law, (iii) under Section 174 of the DGCL, or (iv) for any transaction from which the director derived an improper personal benefit. If the DGCL is amended after the effective date of this Amended and Restated Certificate of Incorporation to authorize corporate action further eliminating or limiting the personal liability of directors, then the liability of a director of the Corporation shall be eliminated or limited to the fullest extent permitted by the DGCL, as so amended.

Any amendment, modification or repeal of the foregoing paragraph shall not adversely affect any right or protection of a director of the Corporation hereunder in respect of any act or omission occurring prior to the time of such amendment, modification or repeal.

EIGHTH. Subject to the rights of the holders of any series of Preferred Stock, stockholders of the Corporation may not take any action by written consent in lieu of a meeting.

NINTH. Special meetings of stockholders may be called at any time only by a majority of the Board of Directors. Business transacted at any special meeting of stockholders shall be limited to matters relating to the purpose or purposes stated in the notice of meeting.

TENTH. In furtherance and not in limitation of the powers conferred upon it by the laws of the State of Delaware, the Board of Directors shall have the power to adopt, amend, alter or repeal the Corporation’s Bylaws. The affirmative vote of a majority of the directors present at any regular or special meeting of the Board of Directors at which a quorum is present shall be required to adopt, amend, alter or repeal the Corporation’s Bylaws. The Corporation’s Bylaws also may be adopted, amended, altered or repealed by the stockholders; provided, however, that in addition to any vote of the holders of any class or series of stock of the Corporation required by law or by this Amended and Restated Certificate of Incorporation, the affirmative

5

vote of the holders of at least sixty-six and two-thirds percent (66 2/3%) of the voting power of all of the then outstanding shares of the capital stock of the Corporation entitled to vote generally in the election of directors, voting together as a single class shall be required to adopt, amend, alter or repeal any provisions of the Bylaws of the Corporation.

ELEVENTH. The Corporation reserves the right at any time, and from time to time, to amend, alter, change or repeal any provision contained in this Amended and Restated Certificate of Incorporation, and other provisions authorized by the laws of the State of Delaware at the time in force may be added or inserted, in the manner now or hereafter prescribed by law; and all rights, preferences and privileges of whatsoever nature conferred upon stockholders, directors or any other persons whomsoever pursuant to this Amended and Restated Certificate of Incorporation in its present form or as hereafter amended are granted subject to the rights reserved in this article.

TWELFTH. Notwithstanding anything to the contrary elsewhere contained in this Amended and Certificate of Incorporation or any provision of law that might otherwise permit a lesser or no vote, but in addition to any vote of the holders of any class or series of stock of the Corporation required by law or this Amended and Restated Certificate of Incorporation and subject to Section A(4) of Article Fourth of this Amended and Restated Certificate of Incorporation, the affirmative vote of the holders of at least sixty-six and two-thirds percent (66 2/3%) of the voting power of all of the then outstanding shares of the capital stock of the Corporation entitled to vote generally in the election of directors, voting together as a single class, shall be required to alter, amend or repeal the following Articles of this Amended and Restated Certificate of Incorporation: Articles FIFTH, SIXTH, SEVENTH, EIGHTH, NINTH, TENTH, ELEVENTH AND TWELFTH or to adopt any provision of this Amended and Restated Certificate of Incorporation or of the Corporation’s Bylaws in a manner that is inconsistent with the purpose and intent of the foregoing provisions.

* * * * *

6