Exhibit 3.1

THIRD AMENDED AND RESTATED

CERTIFICATE OF INCORPORATION

OF

AFFINION GROUP HOLDINGS, INC.

(Dated December 11, 2013)

THIS THIRD AMENDED AND RESTATED CERTIFICATE OF INCORPORATION of Affinion Group Holdings, Inc., a corporation organized and existing under the laws of the State of Delaware (the “Corporation”), has been duly adopted by the stockholders and the Board of Directors of the Corporation (the “Board”) in accordance with Sections 228, 242 and 245 of the General Corporation Law of the State of Delaware (the “DGCL”) and expressly supersedes and replaces in its entirety that certain Second Amended and Restated Certificate of Incorporation, filed with the Secretary of State of the State of Delaware on October 19, 2011. The original name of the Corporation was “Affinity Acquisition Holdings, Inc.”, and the Corporation was incorporated on July 14, 2005 by the filing of the original Certificate of Incorporation with the Secretary of State for the State of Delaware.

NOW, THEREFORE, the text of the Corporation’s Second Amended and Restated Certificate of Incorporation hereby is amended and restated in its entirety to read as follows:

ARTICLE I

The name of the Corporation is Affinion Group Holdings, Inc.

ARTICLE II

The address of the registered office of the Corporation in the State of Delaware is 2711 Centerville Road, Suite 400, Wilmington, County of New Castle, Delaware 19808. The name of the registered agent of the Corporation at such address is Corporation Service Company.

ARTICLE III

The purpose for which the Corporation is organized is to engage in any lawful act or activity for which corporations may be organized under the DGCL and to possess and exercise all of the powers and privileges granted by such law and any other law of the State of Delaware.

ARTICLE IV

The total number of shares of all classes of stock which the Corporation shall have authority to issue is 550,000,000, consisting of 540,000,000 shares of Common Stock, par value $0.01 per share (the “Common Stock”) and 10,000,000 shares of Preferred Stock, par value $0.01 per share (the “Preferred Stock”) (collectively with the Common Stock , the “Capital Stock”). In addition, the Corporation shall have the authority to issue up to 20,000,000 warrants to purchase shares of Class B Common Stock (the “Series A Warrants”). The Common Stock

shall be divided into two classes as follows: (a) Class A Common Stock, of which the Corporation shall have the authority to issue 360,000,000 shares (collectively, the “Class A Common Stock”) and (b) Class B Common Stock, of which the Corporation shall have the authority to issue 180,000,000 shares (collectively, the “Class B Common Stock”).

The following is a statement of the designations, preferences, voting powers, qualifications, special or relative rights and privileges in respect of the authorized capital stock of the Corporation.

(a) Common Stock.

(1) Rights and Privileges. Except as expressly set forth otherwise herein, the Common Stock shall have (i) all rights and privileges typically associated with such securities as set forth in the DGCL, including, without limitation, the right to receive dividends, the right to vote, subject to Article IV(a)(3)(ii), on all matters presented to the holders of the Common Stock for a vote and the rights upon a liquidation and (ii) the additional rights and privileges hereinafter set forth. Except as expressly set forth otherwise herein, the Class A Common Stock and Class B Common Stock shall be identical in every respect, and the rights and privileges of the holders thereof shall be identical (including with respect to dividends and distributions and rights upon a liquidation).

(2) Dividends. Subject to the rights of the Preferred Stock, dividends may be paid on the Common Stock, as and when declared by the Board, out of the assets of the Corporation legally available for the payment of such dividends (it being understood that any dividends will be declared equally on the Class A Common Stock and Class B Common Stock). If and when dividends on the Common Stock are declared payable from time to time by the Board, whether payable in cash, in property or in shares of capital stock of the Corporation, the holders of Common Stock shall be entitled to share equally, pro rata, based on the number of shares of Common Stock held by each such holder, in such dividends; provided, that, in the case of a dividend or other distribution in Common Stock, the holders of the Class A Common Stock shall receive shares of Class A Common Stock and the holders of Class B Common Stock shall receive shares of Class B Common Stock.

(3) Voting.

(i) Except as otherwise set forth herein, the holders of the Class A Common Stock and the Class B Common Stock shall vote together as a single class on all matters presented to the holders of Common Stock for a vote. Unless otherwise required by applicable law and subject to the Warrantholder Rights Agreement, prior to a Control Event, each share of Common Stock shall, subject to Article IV(a)(3)(ii), entitle the holder thereof to cast one vote. Unless otherwise required by applicable law and subject to the Warrantholder Rights Agreement, after a Control Event, each share of Class A Common Stock shall entitle the holder thereof to cast one vote and each share of Class B Common Stock shall entitle the holder thereof to cast a number of votes equal to the product of (A) a fraction, the numerator of which is one and the denominator of which is

2

the total number of outstanding shares of Class B Common Stock assuming the exercise of all outstanding Warrants multiplied by (B) the difference between (1) a fraction, the numerator of which is the total number of outstanding shares of Class A Common Stock as of immediately after the Control Event and the denominator of which is 49.9% minus (2) the total number of outstanding shares of Class A Common Stock as of immediately after the Control Event. Notwithstanding the foregoing, and subject to (x) the Class B Voting Right, (y) the rights of the Preferred Stock and (z) the right of the Class B Common Stock to nominate and elect the Series A Holders Director, the holders of Class A Common Stock shall have the sole right to vote in the election of Directors.

(ii) Notwithstanding anything to the contrary herein, no Person shall be entitled to vote any shares of Common Stock on any matter, including without limitation pursuant to the Class B Voting Right, unless such Person has delivered evidence reasonably satisfactory to the Corporation that (i) such Person has completed and submitted all material filings, registrations or other notifications to any Governmental Entity that may be required pursuant to applicable Law in connection with the ownership or voting of such Person’s Common Stock entitled to vote on such matter and (ii) all necessary and material approvals or waivers, as the case may be, of any Governmental Entity that may be required pursuant to applicable Law in connection with the ownership or voting of such Person’s Common Stock entitled to vote on such matter have been obtained, including, if applicable, the approval of the Insurance Commissioner and the FCA.

(4) Advance Notice. Notwithstanding anything to the contrary, the holders of Common Stock need not comply with the advance notice provisions set forth in Section 2.10 of the By-Laws (as defined below) to nominate a Director in accordance with this Article IV(a). Notice shall be provided to the Corporation (i) in the case of a regularly scheduled stockholder meeting, at least five Business Days prior to such meeting and (ii) in the case of a special meeting of stockholders, prior to the later of 48 hours after delivery of notice of such meeting and five Business Days prior to such meeting.

(5) Control Event. Notwithstanding anything to the contrary, if a Control Event shall have occurred, then: (A) all of the Directors serving immediately prior to such Control Event shall ipso facto be removed from office (other than the Series A Holders Director, who shall thereafter be deemed to be one of the Directors elected pursuant to the Class B Voting Right (as defined below)) and (B) thereafter the holders of shares of Class B Common Stock shall be entitled to nominate a number of Directors equal to a majority of the total number of Directors and vote, subject to Article IV(a)(3)(ii), separately as a class for the election of such Directors (the “Class B Voting Right”).

(6) Removal of Directors. Subject to the Warrantholder Rights Agreement, a Director may only be removed at the direction of the stockholders that are entitled to elect such Director. For the avoidance of doubt, and subject to the Warrantholder Rights Agreement, (A) holders of shares of Class B Common Stock shall have the sole right to remove any Director elected by such holders (including any Director elected by such holders pursuant to the Class B Voting Right and, following the Control Event, the Series

3

A Holders Director), (B) prior to December 12, 2017 (the “Control Event Date”), the Series A Holders shall have the sole right to remove the Series A Holders Director and (C) holders of Class A Common Stock shall have the sole right to remove any other Director.

(7) Vacancies. Subject to the Warrantholder Rights Agreement and the Stockholders Agreement, the vacancy created by any former Director may only be filled by the stockholders that were entitled to elect such former Director; provided, that, if any stockholders subsequently lost the right to elect such Director, the resulting vacancy shall be filled in accordance with this Article IV(a).

(8) Adjustment. If the Corporation shall in any manner split, subdivide or combine the outstanding shares of Class A Common Stock or Class B Common Stock (an “Adjustment Event”), the outstanding shares of each other class of Common Stock shall be proportionally subdivided or combined in the same manner and on the same basis as the outstanding shares of the other class of Common Stock have been split, subdivided or combined. Promptly after the occurrence of an Adjustment Event, the Corporation shall deliver a notice to each holder of Common Stock setting forth the number of shares into which each share of each class would be convertible into.

(b) Automatic Conversion of Class B Common Stock into Class A Common Stock.

(1) Immediately prior to the consummation of a Qualified Public Offering, (A) each share of Class B Common Stock shall be converted automatically into one share of Class A Common Stock and (B) thereafter the Corporation shall be prohibited from issuing or reissuing any shares of Class B Common Stock.

(2) The Corporation shall, so long as any shares of Class B Common Stock are outstanding, reserve and keep available out of its authorized and unissued Common Stock, solely for the purpose of effecting the conversion of the Class B Common Stock, such number of shares of Class A Common Stock equal to the aggregate number of shares of Class A Common Stock as shall from time to time be sufficient to effect the conversion of all of the Class B Common Stock then outstanding.

(c) Preferred Stock. Subject to the provisions of this Article IV, the Preferred Stock may be issued from time to time in one or more classes or series. The Board shall have the authority to the fullest extent permitted under the DGCL to adopt by resolution from time to time one or more certificates of designations providing for the designation of one or more classes or series of the Preferred Stock and the voting powers, whether full or limited or no voting powers, and such designations, preferences and relative, participating, optional, or other special rights and qualifications, limitations or restrictions thereof, and to fix or alter the number of shares comprising any such class or series, subject to any requirements of the DGCL and this Third Amended and Restated Certificate of Incorporation, as amended from time to time.

The authority of the Board with respect to each such class or series shall include, without limitation of the foregoing, the right to determine and fix the following preferences and powers, which may vary as between different classes or series of the Preferred Stock:

(1) the distinctive designation of such class or series and the number of shares to constitute such class or series;

4

(2) the rate at which dividends on the shares of such class or series shall be declared and paid, or set aside for payment, whether dividends at the rate so determined shall be cumulative or accruing, and whether the shares of such class or series shall be entitled to any participating or other dividends in addition to dividends at the rate so determined, and if so, on what terms;

(3) the right or obligation, if any, of the Corporation to redeem shares of the particular class or series of the Preferred Stock, and, if redeemable, the price, terms and manner of such redemption;

(4) the special and relative rights and preferences, if any, and the amount or amounts per share, which the shares of such class or series of the Preferred Stock shall be entitled to receive upon any voluntary or involuntary liquidation, dissolution or winding up of the Corporation;

(5) the terms and conditions, if any, upon which shares of such class or series shall be convertible into, or exchangeable for, shares of capital stock of any other class or series, including the price or prices or the rate or rates of conversion or exchange and the terms of adjustment, if any;

(6) the obligations, if any, of the Corporation to retire, redeem or purchase shares of such class or series pursuant to a sinking fund or fund of a similar nature or otherwise, and the terms and conditions of such obligation;

(7) voting rights, if any, including special voting rights with respect to the election of directors and matters adversely affecting any class or series of the Preferred Stock;

(8) limitations, if any, on the issuance of additional shares of such class or series or any shares of any other class or series of the Preferred Stock; and

(9) such other preferences, powers, qualifications, special or relative rights and privileges thereof as the Board, by the vote of the members of the Board then in office acting in accordance with this Third Amended and Restated Certificate of Incorporation, or any Preferred Stock, may deem advisable and are not inconsistent with law, the provisions of this Third Amended and Restated Certificate of Incorporation or the provisions of any certificate of designations.

(d) Series A Warrants.

(1) Unless otherwise required by applicable law and subject to the Warrantholder Rights Agreement, prior to the Control Event Date, the holders of Series A Warrants (having one vote per share issuable upon the exercise thereof), together with the holders of Class B Common Stock (having one vote per share) issued upon the exercise of Series A Warrants (collectively, the “Series A Holders”), shall have the right

5

to nominate and elect one director (the “Series A Holders Director”) and vote, subject to Article IV(a)(3)(ii), separately as a single class for the election of the Series A Holders Director.

(2) Except as expressly set forth in the Warrantholders Rights Agreement, the Series A Warrants shall have no other rights, preferences or privileges, including without limitation the right to vote on any matters submitted to stockholders for approval, the right to participate in dividends or distributions or the right to participate in the proceeds of any liquidation or dissolution of the Corporation.

(e) Certain Restrictions on Transfer. Unless otherwise expressly approved by the Board, prior to the consummation of a Qualified Public Offering, no shares of Common Stock shall be Transferred (i) if such Transfer would constitute a violation of applicable laws, (ii) to any Person who is not an “accredited investor” (as such term is defined under Rule 501(a) of Regulation D under the Securities Act) if, at the time of such Transfer, or as a result of giving effect to such Transfer, the Corporation has more than 450 “holders of record” of Common Stock assuming the exercise of all outstanding options to purchase shares of Common Stock or (iii) to any Person if, at the time of such Transfer, or as a result of giving effect to such Transfer, the Corporation has more than 1,900 “holders of record” of Common Stock assuming the exercise of all outstanding options to purchase shares of Common Stock or (iii) if such Transfer would otherwise require the Corporation to register any class of Common Stock under the Exchange Act or any other applicable federal or state securities laws; provided that, the term “holders of record” shall having the meaning ascribed thereto for the purposes of Section 12 (g) of the Exchange Act. For the avoidance of doubt, solely for these purposes, and not for any other purposes, including without limitation the obligation to register securities and become a public reporting company pursuant to Section 12(g) of the Exchange Act, the Class B Common Stock and Class A Common Stock shall be deemed a single class of securities.

(f) Reclassification. Pursuant to this Third Amended and Restated Certificate of Incorporation, each share of common stock of the Corporation outstanding immediately prior to the effectiveness of this Third Amended and Restated Certificate of Incorporation shall be reclassified and exchanged, effective immediately, into one share of Class A Common Stock.

(g) Defined Terms. For purposes of this Third Amended and Restated Certificate of Incorporation:

(1) “Affiliate” shall have the meaning ascribed thereto in the Warrantholder Rights Agreement.

(2) “Business Day” means any day other than a Saturday, a Sunday or a day on which banks in New York, New York are authorized or obligated by Law or executive order to close.

(3) “Control Event” shall have the meaning ascribed thereto in the Warrant Agreement.

6

(4) “Exchange Act” means the Securities Exchange Act of 1934, as amended, and the rules and regulations of the Securities and Exchange Commission promulgated thereunder from time to time.

(5) “FCA” means the U.K. Financial Conduct Authority.

(6) “Governmental Entity” means any U.S. or non-U.S. federal, national, supranational, state, provincial, local or similar government, governmental, regulatory or administrative authority, branch, agency or commission or any court, tribunal, or arbitral or judicial body.

(7) “Insurance Commissioner” means the Commissioner of Insurance of the State of North Dakota.

(8) “Law” means any statute, law, ordinance, regulation, rule, code, executive order, injunction, judgment, decree or order of any Governmental Entity.

(9) “Person” shall be construed broadly and shall include, without limitation, an individual, a partnership, a limited liability company, a corporation, an association, a joint stock company, a trust, a joint venture, an unincorporated organization and a government entity.

(10) “Qualified Public Offering” shall have the meaning ascribed thereto in the Warrantholder Rights Agreement.

(11) “Stockholder Agreement” means that certain Stockholder Agreement, dated as of January 14, 2011, by and among the Corporation and the other holders party thereto, as amended by that certain amendment dated as of the date hereof.

(12) “Transfer” means any direct or indirect sale, assignment, transfer, conveyance, gift, bequest by will or under intestacy laws, pledge, hypothecation or other encumbrance, or any other disposition, of the stated security (or any interest therein or right thereto, including the issuance of any total return swap or other derivative whose economic value is primarily based upon the value of the stated security) or of all or part of the voting power (other than the granting of a revocable proxy) associated with the stated security (or any interest therein) whatsoever, or any other transfer of beneficial ownership of the stated security, with or without consideration and whether voluntarily or involuntarily (including by operation of law). Notwithstanding anything to the contrary set forth herein, transfers of an interest in any member of the Apollo Group (other than any SPV Affiliate) or in the General Atlantic Group (other than any SPV Affiliate) shall not be deemed to be a Transfer.

(13) “Warrants” shall have the meaning ascribed thereto in the Warrant Agreement.

(14) “Warrant Agreement” means, that certain Warrant Agreement, dated on or about December 12, 2013, by and between the Corporation and Wells Fargo Bank, National Association, as warrant agent.

(15) “Warrantholder Rights Agreement” means that certain Warrantholder Rights Agreement, dated on or about December 12, 2013, by and among the Corporation and the investors party thereto.

7

ARTICLE V

In furtherance and not in limitation of the powers conferred by the laws of the State of Delaware, the Board is expressly authorized and empowered to make, alter, amend or repeal the By-Laws of the Corporation (as they may be amended, restated, supplemented or otherwise revised from time to time, the “By-Laws”) in any manner not inconsistent with the laws of the State of Delaware or this Third Amended and Restated Certificate of Incorporation.

ARTICLE VI

The stockholders shall have the right to elect a number of directors of the Board (as set forth in the Stockholder Agreement and the Warrantholder Rights Agreement) to be designated as the directors of the Corporation (the “Directors”), in accordance with the By-Laws, the Stockholder Agreement and the Warrantholder Rights Agreement. The number of Directors may be increased or decreased from time to time as provided in the By-Laws, the Stockholder Agreement and the Warrantholder Rights Agreement. Each of the Directors shall hold office until a qualified successor is elected at the next annual meeting of stockholders or, if earlier, such Director’s death, resignation or removal pursuant to the By-Laws, the Stockholder Agreement and the Warrantholder Rights Agreement. With respect to each matter brought before the Board (or any committee thereof) for vote, each Director shall be entitled to cast one vote.

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 (a) for any breach of the Director’s duty of loyalty to the Corporation or its stockholders, (b) for acts or omissions not in good faith or which involve intentional misconduct or a knowing violation of law, (c) under Section 174 of the DGCL, or (d) for any transaction from which the Director derived any improper personal benefit. If the DGCL is amended after the date of incorporation of the Corporation 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.

The Corporation hereby acknowledges that certain Directors (the “Specified Persons”) may have rights to indemnification and advancement of expenses provided by a stockholder of the Corporation or its affiliates (directly or through insurance obtained by any such entity) (collectively, the “Stockholder Indemnitors”). The Corporation hereby agrees and acknowledges that (i) it is the indemnitor of first resort with respect to the Specified Persons, (ii) it shall be required to advance the full amount of expenses incurred by the Specified Persons, as required by the terms of these By-Laws, without regard to any rights the Specified Persons may have against the Stockholder Indemnitors and (iii) it irrevocably waives, relinquishes and releases the Stockholder Indemnitors from any and all claims against the Stockholder Indemnitors for contribution, subrogation or any other recovery of any kind in respect thereof. The Corporation further agrees that no advancement or payment by the Stockholder Indemnitors on behalf of the Corporation with respect to any claim for which the Specified Persons have sought

8

indemnification from the Corporation shall affect the foregoing and the Stockholder Indemnitors shall have a right of contribution and/or be subrogated to the extent of such advancement or payment to all of the rights of recovery of the Specified Persons against the Corporation. These rights shall be a contract right.

Any repeal or modification of any of the foregoing paragraphs in this Article VI by the stockholders of the Corporation shall not adversely affect any right or protection of a Director of the Corporation existing at the time of such repeal or modification.

ARTICLE VII

The Corporation shall, to the fullest extent permitted by the provisions of Section 145 of the DGCL, as the same now exists or may be amended and supplemented, indemnify and advance expenses to its Directors and officers, both as to action in his or her official capacity and as to action in another capacity while holding such office. The Corporation may, by action of the Board, extend such indemnification and advancement of expenses to any and all persons whom it shall have power to indemnify, including but not limited to its employees or agents, on such terms and conditions and to the extent determined by the Board in its sole and absolute discretion. The indemnification and advancement of expenses provided for herein shall not be deemed exclusive of any other rights to which those indemnified may be entitled under any bylaw, agreement, vote, of the stockholders or disinterested Directors or otherwise and shall continue as to any person who has ceased to be a Director, officer, employee or agent and shall inure to the benefit of the heirs, executors, and administrators of such person. The Corporation shall have the power to purchase and maintain insurance on behalf of any person who is or was a Director, officer, employee or agent of the Corporation against any liability asserted against him or her and incurred by him or her in any such capacity, or arising out of his or her status as such, whether or not the Corporation would have the power to indemnify him or her against such liability under this Article VII.

Any amendment, repeal or modification of the foregoing paragraph, or the adoption of any provision inconsistent with this Article VII, shall not adversely affect any right or protection existing at the time of such amendment, repeal, modification or adoption.

ARTICLE VIII

To the maximum extent permitted from time to time under the DGCL, the Corporation renounces any interest or expectancy of the Corporation in, or in being offered an opportunity to participate in, any and all business opportunities that are presented to any of its stockholders or Directors (other than in their capacity as a Director and other than those Directors who are employees of the Corporation).

Without limiting the foregoing renunciation, the Corporation acknowledges that certain of the stockholders are in the business of making investments in, and have investments in, other businesses similar to and that may compete with the Corporation’s businesses (“Competing Businesses”), and agrees that each such Stockholder shall have the right to make additional investments in or have relationships with other Competing Businesses independent of its investment in the Corporation. No stockholder that has designated a Director shall be obligated

9

to present to the Corporation any particular investment opportunity that such Director or stockholder gains access to, other than by reason of such Director’s status as a Director (and other than those Directors who are employees of the Corporation), even if such opportunity is of a character that, if presented to the Corporation or one of its subsidiaries, could be taken by the Corporation or such subsidiary, and such Director or stockholder shall continue to have the right to take for such Director’s or stockholder’s own respective account or to recommend to others any such particular investment opportunity.

The provisions of this Article VIII shall in no way limit or eliminate any such stockholder’s duties, responsibilities and obligations with respect to the protection of any proprietary information of the Corporation and any of its subsidiaries, including any applicable duty not to disclose or use such proprietary information improperly or to obtain therefrom an improper personal benefit.

No amendment or repeal of this Article VIII shall apply to or have any effect on the liability or alleged liability of any Director of the Corporation for or with respect to opportunities of which such Director becomes aware prior to such amendment or repeal.

ARTICLE IX

The Corporation elects not to be governed by Section 203 of the DGCL.

ARTICLE X

The Corporation reserves the right to amend this Third Amended and Restated Certificate of Incorporation in any manner permitted by the DGCL, as the same exists or may hereafter be amended, and any rights and powers conferred upon stockholders, Directors and officers herein are granted subject to this reservation.

*  *  *  *  *   *

10

IN WITNESS WHEREOF, the undersigned authorized officer of the Corporation has duly executed this Third Amended and Restated Certificate of Incorporation as of the date first written above.