Exhibit 10.4

THIS WARRANT AND ANY SECURITIES ACQUIRED UPON THE EXERCISE OF THIS WARRANT HAVE BEEN OR WILL BE ACQUIRED FOR INVESTMENT AND HAVE NOT BEEN REGISTERED UNDER THE SECURITIES ACT OF 1933, AS AMENDED (THE “ACT”), OR UNDER THE SECURITIES LAWS OF ANY STATE OR OTHER JURISDICTION. NEITHER THESE SECURITIES NOR ANY INTEREST OR PARTICIPATION HEREIN MAY BE REOFFERED, SOLD, ASSIGNED, TRANSFERRED, PLEDGED, ENCUMBERED OR OTHERWISE DISPOSED OF IN THE ABSENCE OF SUCH REGISTRATION OR AN EXEMPTION THEREFROM PURSUANT TO THE ACT AND APPLICABLE STATE SECURITIES LAWS. ANY OFFER, SALE, ASSIGNMENT, TRANSFER OR OTHER DISPOSITION OF THIS WARRANT OR ANY SECURITIES ACQUIRED UPON THE EXERCISE OF THIS WARRANT IN A TRANSACTION THAT IS NOT REGISTERED UNDER THE ACT IS SUBJECT TO THE COMPANY’S RIGHT TO REQUIRE DELIVERY OF AN OPINION OF COUNSEL TO THE EFFECT THAT ANY PROPOSED TRANSFER OR RESALE IS IN COMPLIANCE WITH THE ACT AND ANY APPLICABLE STATE SECURITIES LAWS.

THIS WARRANT AND ANY SECURITIES ACQUIRED UPON THE EXERCISE OF THIS WARRANT ARE SUBJECT TO THE TERMS OF (I) A STOCKHOLDER AGREEMENT DATED AS OF JANUARY 14, 2011 (AS IT MAY BE AMENDED, MODIFIED, SUPPLEMENTED OR RESTATED FROM TIME TO TIME, THE “STOCKHOLDER AGREEMENT”), AMONG THE HOLDER OF THIS WARRANT (OR THE PREDECESSOR IN INTEREST TO THE HOLDER OF THIS WARRANT), THE COMPANY AND CERTAIN OTHER STOCKHOLDERS OF THE COMPANY, AND (II) A CALL AGREEMENT DATED AS OF JANUARY 14, 2011 (AS IT MAY BE AMENDED, MODIFIED, SUPPLEMENTED OR RESTATED FROM TIME TO TIME, THE “CALL AGREEMENT”), AMONG THE HOLDER OF THIS WARRANT (OR THE PREDECESSOR IN INTEREST TO THE HOLDER OR THIS WARRANT), THE COMPANY, AFFINION GROUP HOLDINGS, LLC, GENERAL ATLANTIC PARTNERS 79, L.P. AND FERNANDES FAMILY TRUST A DATED JUNE 25, 1999. THE TERMS OF THE STOCKHOLDER AGREEMENT AND CALL AGREEMENT INCLUDE, AMONG OTHER THINGS, RESTRICTIONS ON TRANSFERS. THE COMPANY WILL, UPON WRITTEN REQUEST, FURNISH A COPY OF SUCH AGREEMENT TO THE HOLDER HEREOF WITHOUT CHARGE.”

WARRANT

TO PURCHASE SHARES OF COMMON STOCK,

PAR VALUE $0.01 PER SHARE,

OF

AFFINION GROUP HOLDINGS, INC.

This certifies that, for good and valuable consideration, Affinion Group Holdings, Inc., a Delaware corporation (the “Company”), grants to Richard Fernandes (the “Warrantholder”), the

right during the Exercise Period (as hereinafter defined) to subscribe for and purchase from the Company [—] validly issued, fully paid and nonassessable shares, par value $0.01, of Common Stock of the Company (the “Warrant Shares”) (such aggregate number of Warrant Shares issuable hereunder, the “Aggregate Number”), at the exercise price per share (the “Exercise Price”) of $[—] subject to the terms, conditions and adjustments herein set forth. Capitalized terms used herein shall have the meanings ascribed to such terms in Section 8 below.

1.1 Exercise of Warrant. Subject to the terms and conditions set forth herein, this Warrant may be exercised at any time, in whole or in part, by the Warrantholder during the Exercise Period by:

(a) the surrender of this Warrant to the Company, with a duly executed Exercise Form, and

(b) the delivery to the Company of the aggregate Exercise Price by cash, wire transfer, certified or official bank check or any other means approved by the Company, in lawful money of the United States of America.

The Company agrees that the Warrant Shares shall be deemed to be issued to the Warrantholder as the record holder of such Warrant Shares as of the close of business on the date on which this Warrant shall have been surrendered and payment made for the Warrant Shares as aforesaid.

1.2 Payment of Taxes. The Company will pay all documentary stamp or other issuance taxes, if any, attributable to the issuance of Warrant Shares upon the exercise of this Warrant; provided, however, that the Company shall not be required to pay any taxes which may be payable in respect of any transfer involved in the issue or delivery of any Warrants or Warrant certificates or Warrant Shares in a name other than that of the then Warrantholder as reflected upon the books of the Company. In addition, prior to the delivery of a certificate or certificates representing the Warrant Shares, the Warrantholder must pay to the Company in the form of cash, wire transfer, certified or official bank check or any other lawful means approved by the Company by majority vote of the Board, any such additional amount as the Company determines that it is required to withhold under applicable federal, state or local tax laws in respect of the exercise or the transfer of Warrant Shares.

2. Restrictive Legend. Except as otherwise permitted by this Section 2, each Warrant (and each Warrant issued in substitution for any Warrant pursuant to Section 5) shall be stamped or otherwise imprinted with a legend in substantially the form as set forth on the cover of this Warrant. Notwithstanding the foregoing, the Warrantholder may require the Company to issue a certificate for Warrant Shares without a legend, if either (i) such Warrant Shares have been registered for resale under the Securities Act, (ii) the Warrantholder has delivered to the Company an opinion of legal counsel (from a firm reasonably satisfactory to the Company) which opinion shall be addressed to the Company and be reasonably satisfactory in form and substance to the Company’s counsel, to the effect that such registration is not required with respect to such Warrant Shares, as the case may be, or (iii) such Warrant Shares may be sold pursuant to Rule 144 of the Act without limitation as to volume or manner of sale.

2

3. Reservation and Registration of Shares. The Company covenants and agrees as follows:

(a) All Warrant Shares that are issued upon the exercise of this Warrant shall, upon issuance, be validly issued and be free from all taxes, liens, security interests, charges, and other encumbrances with respect to the issuance thereof, other than taxes in respect of any transfer occurring contemporaneously with such issue and other than any encumbrances arising under the Stockholder Agreement or Call Agreement.

(b) The Company shall at all times have authorized and reserved, and shall keep available and free from preemptive rights, a sufficient number of shares of Common Stock to provide for the exercise of the rights represented by this Warrant.

4. Anti-dilution Adjustments. The Exercise Price and the number of Warrant Shares to be received upon exercise of this Warrant shall be subject to adjustment as follows:

4.1 Dividend, Subdivision, Combination or Reclassification of Common Stock. In the event that the Company shall at any time or from time to time after the issuance of this Warrant but prior to the exercise hereof, (a) make a dividend or distribution on the outstanding shares of Common Stock payable in Capital Stock, (b) subdivide the outstanding shares of Common Stock into a larger number of shares, (c) combine the outstanding shares of Common Stock into a smaller number of shares or (d) issue any shares of its Capital Stock in a reclassification of the Common Stock (other than any such event for which an adjustment is made pursuant to another clause of this Section 4), then, and in each such case, (i) the Aggregate Number immediately prior to such event shall be adjusted (and any other appropriate actions shall be taken by the Company) so that the Warrantholder shall be entitled to receive upon exercise of this Warrant the number of shares of Common Stock or other securities of the Company that it would have owned or would have been entitled to receive upon or by reason of any of the events described above, had this Warrant been exercised immediately prior to the occurrence of such event and (ii) the Exercise Price payable upon the exercise of this Warrant shall be adjusted by multiplying such Exercise Price immediately prior to such adjustment by a fraction, the numerator of which shall be the number of Warrant Shares issuable upon the exercise of this Warrant immediately prior to such adjustment, and the denominator of which shall be the number of Warrant Shares issuable immediately thereafter. An adjustment made pursuant to this Section 4.1 shall become effective retroactively (x) in the case of any such dividend or distribution, to a date immediately following the close of business on the record date for the determination of holders of shares of Common Stock entitled to receive such dividend or distribution or (y) in the case of any such subdivision, combination or reclassification, to the close of business on the day upon which such corporate action becomes effective.

4.2 Other Changes. In case the Company at any time or from time to time, after the issuance of this Warrant but prior to the exercise hereof, shall take any action affecting its Common Stock similar to or having an effect similar to any of the actions described in Section 4.1 (but not including any action described in such Section) and the Board in good faith determines that it would be equitable in the circumstances to adjust the Exercise Price and Aggregate Number as a result of such action, then, and in each such case, the Exercise Price and Aggregate Number shall be adjusted in such manner and at such time as the Board in good faith determines would be equitable in the circumstances (such determination to be evidenced in a resolution, a certified copy of which shall be mailed to the Warrantholder).

3

4.3 No Adjustment. Notwithstanding anything herein to the contrary, no adjustment under this Section 4 need be made to the Exercise Price or Aggregate Number if the Company receives written notice from the Warrantholder that no such adjustment is required. Notwithstanding any other provision of this Warrant, the Exercise Price shall not be adjusted below the par value of a share of Common Stock.

4.4 Abandonment. If the Company shall take a record of the holders of shares of its Common Stock for the purpose of entitling them to receive a dividend or other distribution, and shall thereafter and before the distribution to stockholders thereof legally abandon its plan to pay or deliver such dividend or distribution, then no adjustment in the Exercise Price or Aggregate Number shall be required by reason of the taking of such record.

4.5 Certificate as to Adjustments. Upon any adjustment in the Exercise Price or Aggregate Number, the Company shall within a reasonable period (not to exceed ten Business Days) following any of the foregoing transactions deliver to the Warrantholder a certificate, signed by a duly authorized officer of the Company, setting forth in reasonable detail the event requiring the adjustment and the method by which such adjustment was calculated and specifying the adjusted Exercise Price and Aggregate Number then in effect following such adjustment.

4.6 Reorganization, Reclassification, Merger, Etc. In case of any capital reorganization or reclassification or other change of outstanding shares of Common Stock (other than a change in par value, or from par value to no par value, or from no par value to par value, or as a result of a subdivision or combination), or in case of any consolidation or merger of the Company with or into another Person (other than a consolidation or merger in which the Company is the resulting or surviving person and which does not result in any reclassification or change of outstanding Common Stock), or in case of any sale or other disposition to another Person of all or substantially all of the assets of the Company (any of the foregoing, a “Transaction”), the Company, or such successor or purchasing Person, as the case may be, shall execute and deliver to each holder of the Warrants evidenced hereby, promptly after effecting any of the foregoing Transactions, a certificate that such holder of Warrants then outstanding shall be entitled thereafter solely to exercise such Warrants into the kind and amount of shares of stock or other securities (of the Company or another issuer) or property or cash receivable upon such Transaction by a holder of the number of shares of Common Stock into which such Warrants could have been exercised immediately prior to such Transaction. The provisions of this Section 4.6 similarly shall apply to successive Transactions.

4.7 Notices. The Company shall mail to the Warrantholder at least five Business Days prior to the applicable date hereinafter specified, a notice stating the date on which any Transaction is expected to be consummated and, if applicable, the date as of which it is expected that holders of Common Stock of record shall be entitled to exchange their Common Stock for shares of stock or other securities or property or cash deliverable upon such Transaction.

4

5. Loss or Destruction of Warrant. Subject to the terms and conditions hereof, upon receipt by the Company of evidence reasonably satisfactory to it of the loss, theft, destruction or mutilation of this Warrant and, in the case of loss, theft or destruction, of such bond or indemnification as the Company may reasonably require, and, in the case of such mutilation, upon surrender and cancellation of this Warrant, the Company will execute and deliver a new Warrant of like tenor.

6. Ownership of Warrant. The Company may deem and treat the person in whose name this Warrant is registered as the holder and owner hereof (notwithstanding any notations of ownership or writing hereon made by anyone other than the Company) for all purposes and shall not be affected by any notice to the contrary.

7. Amendments, etc. Any provision of this Warrant may be amended, modified, supplemented or otherwise altered and the observance thereof waived with the written consent of the Company and the Warrantholder.

8. Definitions. As used herein, unless the context otherwise requires, the following terms have the following respective meanings:

“Affiliate” means any Person who is an “affiliate” as defined in Rule 12b-2 of the General Rules and Regulations under the Securities Exchange Act of 1934, as amended.

“Aggregate Number” has the meaning set forth in the first paragraph of this Warrant.

“Board” means the Board of Directors of the Company.

“Business Day” means any day other than a Saturday, Sunday or other day on which commercial banks in the State of New York are authorized or required by law or executive order to close.

“Capital Stock” means, with respect to any Person, any and all shares, interests, participations, rights in, or other equivalents (however designated and whether voting or non-voting) of such Person’s capital stock and any and all rights, warrants or options exchangeable for or convertible into such capital stock (but excluding any debt security whether or not it is exchangeable for or convertible into such capital stock).

“Call Agreement” means that certain Call Agreement, dated as of January 14, 2011 by and among Richard Fernandes, Fernandes Family Trust A Dated June 25, 1999, the Company, Affinion Group Holdings, LLC and General Atlantic Partners 79, L.P., as the same may be amended, supplemented, restated or otherwise modified from time to time.

“Common Stock” means the Common Stock, par value $0.01 per share, of the Company.

“Company” has the meaning set forth in the first paragraph of this Warrant.

5

“Exercise Form” means an Exercise Form in the form annexed hereto as Exhibit A.

“Exercise Period” means the period commencing on the Original Issue Date and ending on May 12, 2012.

“Exercise Price” has the meaning set forth in the first paragraph of this Warrant.

“Original Issue Date” means January 14, 2011.

“Person” means any individual, firm, corporation, partnership, limited liability company, trust, incorporated or unincorporated association, joint venture, joint stock company, governmental body or other entity of any kind.

“Securities Act” means the Securities Act of 1933, as amended, and the rules and regulations of the Securities and Exchange Commission thereunder.

“Stockholder Agreement” means the Stockholder Agreement, dated as of the Original Issue Date, by and among the Company, the Warrantholder and the other parties listed therein, as the same may be amended, supplemented, restated or otherwise modified from time to time.

“Transaction” has the meaning set forth in Section 4.6 of this Warrant.

“Transfer” has the meaning set forth on the cover of this Warrant.

“Warrant Shares” has the meaning set forth in the first paragraph of this Warrant.

“Warrantholder” has the meaning set forth in the first paragraph of this Warrant.

9. Miscellaneous.

9.1 Entire Agreement. This Warrant (together with the Stockholder Agreement and the Call Agreement) constitutes the entire agreement between the Company and the Warrantholder with respect to the Warrant and supersedes (i) all prior agreements and understanding with respect to the subject matter of this Warrant, and (ii) Warrant No. 4 issued to Warrantholder by Webloyalty Holdings, Inc. on May 12, 2005.

9.2 Binding Effect; Benefits. This Warrant shall inure to the benefit of and shall be binding upon the Company and the Warrantholder and their respective permitted successors and assigns. Nothing in this Warrant, expressed or implied, is intended to or shall confer on any person other than the Company and the Warrantholder, or their respective permitted successors or assigns, any rights, remedies, obligations or liabilities under or by reason of this Warrant. Neither this Warrant nor any interest in this Warrant or this Agreement may be transferred by the Warrantholder to any Person for any reason or at any time.

6

9.3 Headings. The headings in this Warrant are for convenience of reference only and shall not limit or otherwise affect the meaning of this Warrant.

9.4 Notices. All notices, demands and other communications provided for or permitted hereunder shall be made in writing and shall be by registered or certified first-class mail, return receipt requested, electronic mail sent with a request for delivery receipt, facsimile, courier service or personal delivery:

All such notices, demands and other communications shall be deemed to have been duly given when delivered by hand, if personally delivered; when delivered by courier, if delivered by commercial courier service; five Business Days after being deposited in the mail, postage prepaid, if mailed; upon written or electronic confirmation of delivery, if sent by electronic mail; and when receipt is mechanically acknowledged, if sent by facsimile. Any party may by notice given in accordance with this Section 9.4 designate another address or Person for receipt of notices hereunder.

9.5 Severability. Any term or provision of this Warrant which is invalid or unenforceable in any jurisdiction shall, as to such jurisdiction, be ineffective to the

7

extent of such invalidity or unenforceability without rendering invalid or unenforceable the terms and provisions of this Warrant or affecting the validity or enforceability of any of the terms or provisions of this Warrant in any other jurisdiction.

9.6 GOVERNING LAW. THIS WARRANT SHALL BE GOVERNED BY AND CONSTRUED IN ACCORDANCE WITH THE LAWS OF THE STATE OF NEW YORK WITHOUT REGARD TO THE CONFLICTS OF LAW PRINCIPLES THEREOF. Each of the parties agrees that all actions, suits or proceedings arising out of or based upon this Agreement or the subject matter hereof shall be brought and maintained exclusively in the federal and state courts of the State of New York. Each of the parties hereto by execution hereof (a) hereby irrevocably submits to the jurisdiction of the federal and state courts in the State of New York for the purpose of any action, suit or proceeding arising out of or based upon this Agreement or the subject matter hereof and (b) hereby waives to the extent not prohibited by applicable law, and agrees not to assert, by way of motion, as defense or otherwise, in any such action, suit or proceeding, any claim that it is not subject personally to the jurisdiction of the above-named courts, that it is immune from extraterritorial injunction relief or other injunctive relief, that its property is except or immune from attachment or execution, that any such action, suit or proceeding may not be brought or maintained in one of the above-named courts, that any such action, suit or proceeding brought or maintained in one of the above-named courts should be dismissed on grounds of forum non conveniens, should be transferred to any court other than one of the above-named courts, should be stayed by virtue of the tendency of any other action, suit or proceeding in any court other than one of the above-named courts, or that this Agreement or the subject matter hereof may not be enforced in or by any of the above-named courts. Each of the parties hereto hereby consents to service of process in any such suit, action or proceeding in any manner permitted by the laws of the State of New York, agrees that service of process by registered or certified mail, return receipt requested, at the address specified in this Agreement is reasonably calculated to give actual notice and waives and agrees not to assert by way of motion, as defense or otherwise, in any such action, suit or proceeding any claim that service of process made in accordance therewith does not constitute good and sufficient service of process. The provisions of this Section 9.6 shall not restrict the ability of any party to enforce in any court any judgment obtained in a federal or state court of the State of New York.

9.7 No Rights or Liabilities as Stockholder. Nothing contained in this Warrant shall be determined as conferring upon the Warrantholder any rights as a stockholder of the Company or as imposing any liabilities on the Warrantholder to purchase any securities whether such liabilities are asserted by the Company or by creditors or stockholders of the Company or otherwise.

[Remainder of this page intentionally left blank]

8

IN WITNESS WHEREOF, the Company has caused this Warrant to be signed by its duly authorized officer.

Dated: January 14, 2011

[Signature Page to Warrant]

Exhibit A

EXERCISE FORM

(To be executed upon exercise of this Warrant)

The undersigned hereby irrevocably elects to exercise the right, represented by this Warrant, to purchase [    ] shares of Common Stock and herewith tenders payment for such shares to the order of the Company in the amount of $[        ] in accordance with the terms of this Warrant. The undersigned requests that a certificate for such Warrant Shares be registered in the name of the undersigned and that such certificates be delivered to the undersigned’s address below.

The undersigned represents that it is acquiring such shares for its own account for investment and not with a view to or for sale in connection with any distribution thereof (subject, however, to any requirement of law that the disposition thereof shall at all times be within its control).

Dated: [                    ]

[Signature Page to Warrant Exercise Form]