EX-10.4: AMENDED AND RESTATED FEE LETTER

Exhibit 10.4

March 17, 2008

THL Managers VI, LLC
c/o Thomas H. Lee Partners, L.P.
100 Federal Street, 35th Floor
Boston, Massachusetts 02110
Fax No.: (617)  ###-###-####
Attn: Thomas M. Hagerty

MoneyGram Payment Systems Worldwide, Inc.
MoneyGram International Inc.
1500 Utica Avenue South, MS 8020
Minneapolis, Minnesota 55416
Fax No.: (952)  ###-###-####
Attn: Teresa H. Johnson, Esq.

GSMP/GSCP
c/o Goldman, Sachs & Co.
85 Broad Street
New York, New York 10004
Attention: Edward Pallesen

Amended and Restated Fee Letter

Ladies and Gentlemen:

     Reference is hereby made to that certain Contingent Fee Letter, by and between THL MANAGERS VI, LLC (“THL Managers”), GSMP V ONSHORE US, LTD., an exempted company incorporated in the Cayman Islands with limited liability (“GSMP V Onshore”), GSMP V OFFSHORE US, LTD., an exempted company incorporated in the Cayman Islands with limited liability (“GSMP V Offshore”), and GSMP V INSTITUTIONAL US, LTD., an exempted company incorporated in the Cayman Islands with limited liability (“GSMP Institutional and, together with GSMP V Onshore and GSMP V Offshore, “GSMP”), GS CAPITAL PARTNERS VI FUND, L.P., GS CAPITAL PARTNERS VI OFFSHORE FUND, L.P., GS CAPITAL PARTNERS VI GmbH & Co. KG, and GS CAPITAL PARTNERS VI PARALLEL, L.P., and MONEYGRAM PAYMENT SYSTEMS WORLDWIDE, INC., a Delaware corporation (the “Company”), dated as of February 11, 2008 (the “Original Contingent Fee Letter”), which the parties hereby amend and restate in full, as more fully set forth below:

     Reference is made to (a) that certain Amended and Restated Note Purchase Agreement (the “Note Purchase Agreement”), dated as of March 17, 2008, by and between MONEYGRAM INTERNATIONAL, INC., a Delaware corporation (“HoldCo”), the Company, GSMP and THL Credit Partners, L.P., which amended and restated the Note Purchase Agreement as of February 11, 2008 (the “Original Note Purchase Agreement”) dated and (b) that certain Amended and Restated Purchase Agreement (the “Equity Purchase Agreement”), dated as of March 17, 2008, as may be amended, by and between Holdco, GSMP, the parties set forth on Schedule A attached thereto under the heading THL (collectively, “THL”) and the parties set forth on Schedule A attached hereto under the heading Goldman Sachs Capital Partners (collectively, “GSCP” and, together with THL and GSMP, the “Investors”). Capitalized terms used herein and not otherwise defined have the meanings given in the Note Purchase Agreement or Equity Purchase Agreement, as applicable.

	1.		Fee. In connection with the execution of the Original Note Purchase Agreement, the Company deposited into the escrow (the “Escrow”) established pursuant to that certain escrow agreement (the “Original Escrow Agreement”), dated as of February 11, 2008, among the Company, THL Managers VI, LLC (“THL Managers”), GSCP, GSMP and Fried, Frank Harris Shriver & Jacobson, LLP as escrow agent, a deposit with respect to a contingent break-up fee equal to $15,000,000, representing 3.00% of the maximum principal amount of the Notes to be purchased by GSMP pursuant to the Original Note Purchase Agreement (such amount, together with all investment earnings thereon, the “Fee”). On March 14, 2008 the Original Escrow Agreement was amended and restated (the “Escrow Agreement”). Pursuant to the Escrow Agreement, the Bank of New York, or any successor thereto, shall act as escrow agent (the “Escrow Agent”) as of March 14, 2008.
	2.		Payment of Fee. In consideration for amending the Note Purchase Agreement and other consideration (the adequacy of which is hereby acknowledged by the other parties hereto), the parties hereto hereby agree (i) that the Fee shall be disbursed and paid by the Escrow Agent to GSMP on the date hereof and (ii) that, notwithstanding anything to the contrary in the Original Contingent Fee Letter or the Original Note Purchase Agreement or any other document or agreement, in no event shall all or any portion of the Fee be refunded or otherwise repaid to the Company, and the Company shall have no interest therein or claim thereto.
	3.		Subsequent Transaction. If the Equity Purchase Agreement is terminated for any reason and (x) the Company enters into a definitive agreement with respect to, or consummates, any transaction contemplated by a Company Transaction Proposal (other than a transaction entered into or consummated following any voluntary or involuntary petition by Holdco, the Company or any subsidiary of the Company under the federal bankruptcy code (a “Subsequent Transaction”) within nine (9) months of the date of termination of the Equity Purchase Agreement and (y) GSMP provides or commits to provide second lien or subordinated debt financing with respect to the Subsequent Transaction, then, the Fee shall be paid (or retained by GSMP) as follows: (a) if such financing is consummated, GSMP shall pay (or retain, as applicable) the Fee (net of any withholding tax paid by GSMP as a result of its receipt of the Fee) (i) 80 percent to THL Managers and (ii) 20 percent to GSCP and GSMP, pro rata among GSCP and GSMP, in accordance with the aggregate relative purchase price committed to be paid by each of them pursuant to the Equity Purchase Agreement (such allocation, the “80/20 Allocation”), in each case, as promptly as possible, but in any event on the date of the consummation of such Subsequent Transaction and (b) if such financing is not consummated, GSMP shall also pay (or retain, as applicable) the portion of the Fee, if any, equal to any fees paid to and retained by GSMP in connection with such financing (net of any withholding tax paid by GSMP as a result of its receipt of the Fee) to THL, GSCP and GSMP in accordance with the 80/20 Allocation, which such amounts shall be paid on the first date on which GSMP is not subject to any obligation to return or otherwise disgorge such fees.
	4.		Further Agreements. The parties agree to jointly and irrevocably instruct the Escrow Agent, in accordance with the Escrow Agreement, to effect payment of the Fee on the date hereof, by wire transfer in immediately available funds, in accordance with the terms of Section 2 above. Any earnings on the funds deposited in Escrow will be paid to GSMP. To effectuate the foregoing, the Company, THL, GSCP and GSMP have jointly and irrevocably instructed the Escrow Agent as provided in the certificate attached hereto as Exhibit A.
	5.		GOVERNING LAW; JURISDICTION. EACH OF THE PARTIES HERETO IRREVOCABLY AND UNCONDITIONALLY AGREES THAT ANY SUIT OR PROCEEDING ARISING IN RESPECT TO THIS LETTER OR OUR COMMITMENT WILL BE TRIED EXCLUSIVELY

			(SUBJECT TO THE PROVISO BELOW) IN THE U.S. DISTRICT COURT FOR THE SOUTHERN DISTRICT OF NEW YORK OR, IF THAT COURT DOES NOT HAVE SUBJECT MATTER JURISDICTION, IN ANY STATE COURT LOCATED IN THE CITY OF NEW YORK, AND YOU AGREE TO SUBMIT TO THE EXCLUSIVE JURISDICTION OF, AND TO VENUE IN, SUCH COURT. THIS LETTER SHALL BE GOVERNED BY AND CONSTRUED IN ACCORDANCE WITH THE LAWS OF THE STATE OF NEW YORK WITHOUT REGARD TO PRINCIPALS OF CONFLICTS OF LAWS THAT WOULD CAUSE THE APPLICATION OF THE LAWS OF ANOTHER JURISDICTION.
	6.		WAIVER OF JURY TRIAL. ANY RIGHT TO TRIAL BY JURY WITH RESPECT TO ANY ACTION OR PROCEEDING ARISING IN CONNECTION WITH OR AS A RESULT OF EITHER OUR COMMITMENT OR ANY MATTER REFERRED TO IN THIS LETTER IS HEREBY WAIVED BY THE PARTIES HERETO.
	7.		Counterparts. This letter may be executed in counterparts, each of which shall be deemed to constitute an original but all of which shall constitute one and the same instrument. Delivery of an executed signature page of this letter by facsimile, e-mail or similar transmission shall be effective as delivery of a manually executed counterpart hereof.

[SIGNATURE PAGES FOLLOW]

     If the foregoing terms and conditions are acceptable to you, please so indicate by signing both of the enclosed copies of this letter where indicated and returning one to the undersigned, whereupon this letter shall become a binding agreement between us.

Goldman Sachs Mezzanine Partners

Goldman Sachs Capital Partners

THL

Escrow Amount Release Certificate

     This certificate is being delivered pursuant to Section 4 of the Amended and Restated Escrow Agreement, dated as of March 14, 2008 (the “Escrow Agreement”), by and between the Escrow Parties and The Bank of New York, as escrow agent (“Escrow Agent”). Capitalized terms used but not defined herein have the respective meanings specified in the Escrow Agreement. The Escrow Parties hereby jointly certify to the Escrow Agent and direct the Escrow Agent through the undersigned officer as follows:

     The Escrow Agent shall release the Escrow Amount (including any accrued interest) held in the Escrow Account in accordance with the terms of the Escrow Agreement and the Amended and Restated Contingent Fee Letter, dated as of March 17, 2008, by and between the Escrow Parties (the “Contingent Fee Letter”), by wire transfer, as follows:

[Only one payment to be checked]

o To GSMP in accordance with Section 2 of the Contingent Fee Letter.

[REMAINDER OF THIS PAGE INTENTIONALLY LEFT BLANK]

Goldman Sachs Mezzanine Partners

Goldman Sachs Capital Partners

THL