EXHIBIT 10.4

EXECUTION VERSION

NOMINATING AGREEMENT

This Nominating Agreement (as it may be amended from time to time, this “Agreement”) is made as of November 9, 2015 by and between Affinion Group Holdings, Inc., a Delaware corporation (the “Company”), and Third Avenue Trust, on behalf of Third Avenue Focused Credit Fund (“Third Avenue”).

RECITALS

WHEREAS, pursuant to the Certificate (as defined herein), among other things, the Company is authorized to issue capital stock consisting of 550,000,000 shares of Common Stock, par value $0.01 per share (the “Company Common Stock”);

WHEREAS, Third Avenue, together with its Affiliates, holds 1,901,564 shares of Company Common Stock or approximately 19.9% of the Company Common Stock; and

WHEREAS, the Company and Third Avenue desire to enter into this Agreement setting forth certain rights and obligations with respect to the nomination of Directors to the Board of Directors of the Company (the “Board”) and certain other matters relating to the Board as set forth herein as hereinafter provided.

AGREEMENT

NOW, THEREFORE, for good and valuable consideration the receipt and sufficiency of which is hereby acknowledged, the parties to this Agreement intending to be bound hereby agree as follows:

2.1 Third Avenue Nominee.

(a) For purposes of determining the number of Outstanding Company Common Stock held by Third Avenue pursuant to this Section 2.1, the Company Common Stock held by an Affiliate of Third Avenue shall be aggregated with the Company Common Stock held by Third Avenue.

(b) For each Board election occurring after the Regulatory Approval Date, so long as Third Avenue holds in excess of eight percent (8%) of the Outstanding Company Stock (“Third Avenue Threshold”) as of the record date for the applicable Board election or the time a vacancy on the Board is to be filled, as applicable, the Company shall include the Third Avenue Nominee in the Company’s slate of nominees for Director at each annual or special meeting of Stockholders at which Directors are to be elected and at which the Class III Director seats are subject to election. The Company shall use its reasonable best

- 1 -

efforts to cause the election of the Third Avenue Nominee to the Board at such meeting (including recommending that the Company’s Stockholders vote in favor of the election of the Third Avenue Nominee (along with all other Company nominees) and otherwise supporting him or her for election in a manner no less rigorous and favorable than the manner in which the Company supports its other nominees in the aggregate).

(c) If at any time Third Avenue ceases to satisfy the Third Avenue Threshold, (A) Third Avenue shall cause the Third Avenue Nominee then sitting on the Board to resign from the Board with immediate effect; and (B) the vacancy caused by such resignation shall be filled in accordance with the Company’s Charter Documents.

(d) Third Avenue may elect to relinquish its right to nominate a Director by providing the Company with written notice of such election on or prior to the record date for the applicable Board election.

(e) In the event that the Third Avenue Nominee resigns, is removed from the Board (except in the circumstances described in Section 2.1(c)) dies or otherwise is unable to serve on the Board, Third Avenue shall (if, at the time such vacancy is to be filled, Third Avenue still has the right to nominate such Director) be entitled to nominate a successor Director, and the Company shall take any Necessary Action as may be required to facilitate and implement the immediate appointment of such Third Avenue Nominee to the Board.

2.2 Limitations on Amendments to Charter Documents. So long as this Agreement shall remain in effect, the Company shall not cause or permit any amendments to the Bylaws or the Certificate that would conflict with the rights and obligations set forth herein except to the extent required to comply with applicable law.

3.1 Generally. The rights and remedies of any party hereto as set forth in this Agreement are not exclusive and are in addition to any other rights and remedies now or hereafter provided by law or at equity. The parties hereto agree and acknowledge that money damages may not be an adequate remedy for any breach of the provisions of this Agreement and that, in addition to any other rights and remedies at law or in equity existing in its favor, any party hereto shall be entitled to specific performance and/or other injunctive relief from any court of law or equity of competent jurisdiction (without posting any bond or other security) in order to enforce or prevent violation of the provisions of this Agreement.

- 2 -

4.1 Oral Modifications. This Agreement may not be orally amended, modified, extended or terminated, nor shall any oral waiver of any of its terms be effective.

4.2 Written Modifications. Except as otherwise provided herein, the provisions of this Agreement may be amended only with the prior written consent of Third Avenue and the Company.

4.3 Termination. This Agreement shall automatically terminate and be of no further force and effect upon the earlier to occur of (1) a Listing and (2) the first date following the Regulatory Approval Date that Third Avenue is no longer entitled to nominate a director pursuant to Section 2.1(b) as a result of Third Avenue failing to satisfy the Third Avenue Threshold test.

5.1 Certain Matters of Construction. In addition to the definitions referred to or set forth below in this Section 5:

(a) The titles and section headings set forth in this Agreement are for convenience only and shall not be considered as part of agreement of the parties hereto.

(b) When the context requires, the plural shall include the singular and the singular the plural, and any gender shall include all other genders or neuter. The words “include,” “includes” and “including” shall be deemed to be followed by the phrase “without limitation.”

(c) No provision of this Agreement shall be interpreted or construed against any party because such party or its counsel was the drafter thereof. Any reference to statutes or laws will include all amendments, modifications, or replacements of the specific sections and provisions concerned.

(d) Numbered or lettered articles, sections, and subsections herein contained refer to articles, sections, and subsections of this Agreement unless otherwise expressly stated.

(e) The word “including” shall mean including, without limitation.

5.2 Definitions. The following terms shall have the following meanings:

“Affiliate(s)” means any individual, partnership, corporation, trust or other entity or association, directly or indirectly, through one (1) or more intermediaries, controlling, controlled by, or under common control with a Person. The term “control,” as used in the immediately preceding sentence, means, with respect to a corporation or limited liability company the right to exercise, directly or indirectly, ten percent (10%) or more of the voting rights attributable to the controlled corporation or limited liability company, and, with respect to any individual, partnership, trust, other entity or association, the possession, directly or indirectly, of the power to direct or cause the direction of the management or policies of the controlled entity. With respect to any Person who is a general partner of a Person, such general partner is an Affiliate of such Person. With respect to a limited partnership, “Affiliate” shall also mean any limited partner of such limited partnership holding ten percent (10%) or more of the capital or interests in profits of such limited partnership. With respect to a trust, any Affiliate shall include any Person which is a trustee or lifetime beneficiary of such trust.

- 3 -

“Agreement” has the meaning set forth in the Preamble.

“Board” has the meaning set forth in the Recitals.

“Bylaws” means the Fourth Amended and Restated Bylaws of the Company, as amended from time to time.

“Certificate” means the Fourth Amended and Restated Certificate of Incorporation of the Company, as amended from time to time.

“Charter Documents” means, with respect to the Company, the certificate of incorporation and bylaws of the Company, as the same may be amended, supplemented, modified or restated from time to time, and with respect to any other Person, the articles, bylaws, certificate of incorporation, certificate of formation, operating agreement, partnership agreement or any other similar incorporating or formation documents of such Person, as the same may be amended, supplemented, modified or restated from time to time.

“Company” has the meaning set forth in the Preamble.

“Company Common Stock” has the meaning set forth in the Recitals.

“Derivative Securities” has the meaning set forth in the Shareholder Agreement.

“Director” means any member of the Board (other than any Person (if any) effecting observer rights on the Board).

“Equity Incentive Plans” means any equity incentive plans for officers, employees or Directors of the Company.

“Listing” means the listing of the Company Common Stock on a U.S. national securities exchange registered with the US Securities and Exchange Commission.

“Necessary Action” means, with respect to a specified result, all actions that are permitted by law and necessary to cause such result, including (i) recommending that the Company’s Stockholders vote in favor of the election of the Third Avenue Nominee, (ii) agreeing to commercially reasonable amendments to the applicable Charter Documents, (iii) executing agreements and instruments reasonably necessary to permit Third Avenue to exercise its rights hereunder, and (iv) making, or causing to be made, with governmental, administrative or regulatory authorities, all filings, registrations or similar actions that are required to achieve such result, in each case subject to compliance with applicable law.

“Outstanding Company Common Stock” means, as of any given time, the then issued and outstanding Company Common Stock, excluding any Derivative Securities, other than any Limited Warrants, which will be included on an as-exercised basis, and any Company Common Stock issued pursuant to an Equity Incentive Plan.

- 4 -

“Person” means an individual, partnership, limited liability company, corporation, joint venture, trust, business trust, association, or similar entity, whether domestic or foreign, and the heirs, executors, legal representatives, successors and assigns of such entity where the context requires.

“Permitted Transfer” has the meaning set forth in the Stockholder Agreement.

“Regulatory Approval Date” means the date on which the approval set forth on Exhibit A has been obtained by Third Avenue.

“Shareholder Agreement” means the Shareholder Agreement, dated September 29, 2015, by and among the Company and the stockholders party thereto.

“Third Avenue” has the meaning set forth in the Preamble.

“Third Avenue Nominee” means Scott Bernstein or any another Person selected by Third Avenue to serve as the replacement Third Avenue Nominee.

“Third Avenue Threshold” has the meaning set forth in Section 2.1(b).

“Stockholder” has the meaning set forth in the Shareholder Agreement.

6.1 Authority; Effect. Each party hereto represents and warrants to and agrees with each other party that the execution and delivery of this Agreement and the consummation of the transactions contemplated hereby have been duly authorized on behalf of such party and do not violate any agreement or other instrument applicable to such party or by which its assets are bound. This Agreement does not, and shall not be construed to, give rise to the creation of a partnership among any of the parties hereto, or to constitute any of such parties members of a joint venture, group or other association.

6.2 Notices. All notices, requests, demands and other communications required or permitted to be given hereunder shall be in writing and shall be delivered (a) by personal delivery, (b) by a nationally recognized overnight courier service, (c) by telefacsimile or electronic mail, using equipment that provides written confirmation of delivery, or (d) by deposit in the U.S. Mail, postage prepaid, registered or certified mail, return receipt requested, at the address set forth below:

Affinion Group, Inc.

6 High Ridge Park

Stamford, CT 06905

Attention: Brian Fisher, Esq.

Facsimile: 203-956-1206

Electronic mail: bfisher@affiniongroup.com

- 5 -

with a copy (which shall not constitute notice) to:

Akin Gump Strauss Hauer & Feld LLP

One Bryant Park

New York, NY 10036

Attention: Adam Weinstein, Esq.

Facsimile: 212-872-1002

Electronic mail: aweinstein@akingump.com

Third Avenue Trust, on behalf of Third Avenue Focused Credit Fund

622 Third Avenue

32nd Floor

New York, New York 10017

Attention: General Counsel

with a copy (which shall not constitute notice) to:

Milbank Tweed Hadley & McCloy LLP

28 Liberty Street

New York, NY 10011

Attention: Paul Denaro

Facsimile: 212-822-5219

Electronic mail: pdenaro@milbank.com

Any such notice shall be deemed to have been given on the date so delivered, if delivered personally or by overnight courier service or electronic mail; or if by telefacsimile, on the first (1st) day following the transmission of such facsimile; or if mailed, four (4) calendar days after mailing. Any party may, at any time by giving five (5) calendar days’ prior written notice to the Company, specify a different address (physical or electronic) or telefacsimile number for notice purposes by sending notice thereof in the foregoing manner. By notice complying with the foregoing provisions of this Section 6.2, each party shall have the right to change the mailing address, facsimile number or email address for future notices, communications or deliveries to such party pursuant to this Agreement and any such change shall not be deemed an amendment to this Agreement.

6.3 No Assignment. This Agreement may not be transferred or assigned by any party hereto.

6.4 Binding Effect. Subject to the provisions of this Agreement relating to transferability or assignment, this Agreement will be binding upon and inure to the benefit of the Company and Third Avenue, and their respective heirs, devisees, spouses, distributees, representatives, successors and permitted assigns.

- 6 -

6.5 Severability. If any provision of this Agreement is held to be illegal, invalid, or unenforceable under any present or future laws applicable to the Company effective during the term of this Agreement, such provision will be fully severable; this Agreement will be construed and enforced as if such illegal, invalid, or unenforceable provision had never comprised a part of this Agreement; and the remaining provisions of this Agreement will remain in full force and effect and will not be affected by the illegal, invalid, or unenforceable provision or by its severance from this Agreement.

6.6 Additional Documents and Acts. Each party hereto agrees to execute and deliver such additional documents and instruments and to perform such additional acts as may be reasonably necessary or appropriate to effectuate, carry out, and perform all of the terms, provisions, and conditions of this Agreement and the transactions contemplated hereby.

6.7 No Employment Rights. Nothing in this Agreement shall confer upon any Person any right to be employed or to continue employment by the Company or any of its Affiliates, or interfere in any manner with any right of the Company or any of its Affiliates to terminate such employment at any time.

7.1 Governing Law. This Agreement and the rights of the parties hereunder will be governed by, interpreted, and enforced in accordance with the laws of the State of Delaware, without reference to conflicts of law principles.

7.2 Consent to Jurisdiction. The Company and Third Avenue (i) irrevocably submits to the exclusive jurisdiction of any state court in the State of Delaware, and the United States District Court for the District of Delaware (and the appropriate appellate courts), for the purposes of any suit, action or other proceeding arising out of this Agreement and (ii) agrees to commence any such action, suit or proceeding either in the United States District Court for the District of Delaware or if such suit, action or other proceeding may not be brought in such court for jurisdictional reasons, in any state court in the State of Delaware. Notwithstanding the foregoing, any party hereto may commence an action, suit or proceeding with any governmental body anywhere in the world for the sole purpose of seeking recognition and enforcement of a judgment of any court referred to in the first sentence of this Section 7.2. The Company and Third Avenue further (x) agrees that service of any process, summons, notice or document by U.S. registered mail to such party’s respective address set forth in Section 6.2 hereof shall be effective service of process for any action, suit or proceeding in Delaware with respect to any matters to which it has submitted to jurisdiction in this Section 7.2 and (y) irrevocably and unconditionally waives any objection to the laying of venue of any action, suit or proceeding arising out of this Agreement in (A) any state court in the State of Delaware, or (B) the United States District Court for the District of Delaware, and hereby further irrevocably and unconditionally waives and agrees not to plead or claim in any such court that any such action, suit or proceeding brought in any such court has been brought in an inconvenient forum.

- 7 -

7.3 WAIVER OF JURY TRIAL. THE COMPANY AND THIRD AVENUE HEREBY WAIVES, TO THE FULLEST EXTENT PERMITTED BY APPLICABLE LAW, ANY RIGHT IT MAY HAVE TO A TRIAL BY JURY IN ANY LITIGATION DIRECTLY OR INDIRECTLY ARISING OUT OF, INVOLVING OR OTHERWISE IN RESPECT OF THIS AGREEMENT OR THIRD AVENUE’S OWNERSHIP OF COMPANY COMMON STOCK. THE COMPANY AND THIRD AVENUE (i) CERTIFIES THAT NO REPRESENTATIVE, AGENT OR ATTORNEY OF THE COMPANY OR THIRD AVENUE HAS REPRESENTED, EXPRESSLY OR OTHERWISE, THAT THE COMPANY OR THIRD AVENUE WOULD NOT, IN THE EVENT OF LITIGATION, SEEK TO ENFORCE THE FOREGOING WAIVER AND (ii) ACKNOWLEDGES THAT THE COMPANY AND THIRD AVENUE HAS BEEN INDUCED TO ENTER INTO THIS AGREEMENT BY, AMONG OTHER THINGS, THE MUTUAL WAIVERS AND CERTIFICATIONS IN THIS SECTION 7.3.

*    *     Signature pages follow    *    *

- 8 -

IN WITNESS WHEREOF, the Company and Third Avenue have executed this Agreement on the day and year first written above.

[Signature Page to Nominating Agreement (Third Avenue)]

[Signature Page to Nominating Agreement (Third Avenue)]