Exhibit 10.1

TERMINATION AGREEMENT

THIS TERMINATION AGREEMENT (the “Agreement”), entered into as of March 29, 2010, by and between JOHN F. DEPODESTA (the “Executive”) and PRIMUS TELECOMMUNICATIONS GROUP, INCORPORATED and PRIMUS TELECOMMUNICATIONS, INC., both Delaware corporations (together, the “Company”)

RECITALS:

A. Executive has been employed by the Company as Executive Vice President, Chief Legal Officer, Chief Development Officer and Secretary;

B. The parties wish to provide for termination of Executive’s employment with the Company on mutually satisfactory terms with such termination to be effective on March 31, 2010 (the “Termination Date”);

C. Executive and the Company and its subsidiary, Primus Telecommunications, Inc., are parties to a Separation Agreement dated July 1, 2009 (the “Separation Agreement”); and

D. Executive and the Company wish to memorialize the terms for Executive’s termination of employment and set forth their understandings on certain related matters.

Now, Therefore, in consideration of the mutual covenants herein contained, the parties hereto, intending to be legally bound, hereby agree as follows:

1. Termination Date. Executive agrees that his employment with the Company shall terminate effective as of the Termination Date. That termination shall be deemed to be without “Cause” as defined under the Separation Agreement. Effective upon the termination, Executive shall have been deemed to have resigned from all director and officer positions he holds with the Company and any of its affiliates.

2. Payments and Welfare Benefits for Executive.

(a) Provided that the Executive executes the Release attached hereto as Exhibit A (the “Release”) on or before May 30, 2010, and such Release has become effective in accordance with the terms of Section 1(b)(v) thereof, the Company shall pay to Executive the following amounts:

(i) On October 1, 2010, $1,581,225 in a single lump sum, without interest.

(ii) In satisfaction of the Company’s obligations to Executive under Section 2(b)(ii) of the Separation Agreement, the Company shall pay the Executive $10,125 on October 1, 2010, and shall thereafter make 23 monthly payments to Executive of $10,125 each, by the seventh day of each consecutive month, for an aggregate payment under this Section 2(a)(ii) of $243,000.

(iii) All of the premiums for the insurance coverages referenced in Section 2(c) below for the 18 month period commencing on the Termination Date.

(b) The Company shall continue to pay to Executive his current base salary and shall pay any accrued and unused vacation leave through the Termination Date in accordance with the Company’s standard payroll practices. The Company shall also pay to Executive on the Termination Date the sum of $25,000, representing his bonus under the Company’s Executive Bonus Plan for 2009.

(c) Executive shall have the right to elect, and hereby elects, COBRA continuation of care coverage for himself and his spouse under the Company’s dental and vision insurance coverages.

(d) Restricted Stock Units. The Company and Executive hereby stipulate and agree that 39,746 Management Restricted Stock Units (“RSUs”) granted under the Restricted Stock Unit Agreement dated July 2, 2009 (the “RSU Agreement”) are vested and have been exchanged for common stock. In addition, if the “Adjusted EBITDA” (as defined in the RSU Agreement) of the Company for 2010 equals or exceeds ninety percent (90%) of $67,055,000 (Adjusted EBITDA Target), 9,937 of the RSUs shall become vested. The remaining 29,809 unvested or contingent RSU’s are hereby forfeited and terminated. Any additional vested RSUs shall be settled on a one for one basis at the time provided in Section 3 of the RSU Agreement. Except as set forth in this subsection (d), the vested RSUs shall remain subject to the terms of the RSU Agreement and the Company’s Management Compensation Plan.

(e) Non-Qualified Stock Options. The Company and Executive hereby stipulate and agree that 15,264 of the shares of Common Stock issuable under the Non-Qualified Stock Option Agreement dated July 1, 2009 (the “Option Agreement”), are fully vested and exercisable in accordance with the terms of the Option Agreement and the Plan. The remaining portion of such stock options under the Option Agreement are hereby terminated. Except as set forth in this subsection (e), the vested Option shall remain subject to the terms of the Option Agreement and the Company’s Management Compensation Plan.

(f) Performance Based Non-Qualified Stock Option. The Company and the Executive hereby stipulate and agree that 9,937 of the shares of Common Stock issuable under the performance based Non-Qualified Stock Option Agreement dated July 1, 2009 (the “Performance Option Agreement”), are fully vested and exercisable in accordance with the terms of the Performance Option Agreement. In addition, if the “Adjusted EBITDA” (as defined in the Performance Option Agreement) of the Company for 2010 equals or exceeds one hundred and fifteen percent (115%) of $67,055,000 (“Performance Adjusted EBITDA Target”), 2,484 of the shares of Common Stock issuable under the Option Agreement shall become vested. The remaining 7,452 of such stock options under the Performance Option Agreement are hereby terminated. Except as set forth in this subsection (f), the vested Option shall remain subject to the terms of the Performance Option Agreement and the Management Compensation Plan.

(g) Withholding. All compensation and other compensatory benefits provided to Executive pursuant to this Termination Agreement shall be reduced by all amounts required or authorized to be withheld by the Company by applicable federal, state and local law.

-2-

(h) No Additional Benefits. Executive acknowledges and agrees that the payments and other benefits provided for in this Agreement represent the only compensation and benefits to which Executive is entitled and, except for the fees for periods following the Termination Date payable under the Consulting Agreement identified in Section 7 below, Executive is not entitled to any other compensation, remuneration, benefits or entitlements, whether pursuant to the Separation Agreement, Restricted Stock Unit Agreement, Option Agreement or Performance Option Agreement or otherwise, excluding any accrued benefits the Executive may have under the Company’s 401(K) plan.

3. Restrictive Covenants. Executive hereby reaffirms and agrees that all of the terms, restrictions and covenants of Executive set forth in Sections 4, 5, 6, 7 and 8 of the Separation Agreement shall remain in full force and effect in accordance with their terms, without waiver, amendment, or release.

4. Return of Company Property. Except as useful or necessary in performing his duties under the Consulting Agreement, Executive agrees that all files, records, documents, computer disks, drawings, specifications, equipment, keys, credit cards and other property of the Company, including copies thereof, shall be returned to the Company on or before the Termination Date and all such property used by Executive in performing under the Consulting agreement shall be returned to the Company on or before the termination of the Consulting Agreement.

5. Cooperation in Litigation. The Executive agrees to cooperate with and assist the Company in the prosecution or defense of any claims arising out of or related to any matters with which the Executive was involved during his employment with the Company (including, without limitation, attendance at out-of-town proceedings for which the Company may require travel). The Company and Executive shall cooperate in determining mutually acceptable times and locations for Executive to provide such cooperation. The Company agrees to directly pay or reimburse the Executive for the actual expenses incurred by the Executive (including reasonable travel expenses) as a result of his providing such cooperation pursuant to this provision. Following the termination of the Consulting Agreement, the Executive agrees to continue to cooperate with respect to such matters as is reasonably requested and compensated by the Company.

6. Non-Disparagement. Executive and the Company agree that he/it shall not take any actions or make any verbal or written statements to the public, or to the Company’s employees and customers, that disparage the Executive, the Company, its affiliates, officers and directors.

7. Consulting Agreement. The Company and Executive hereby execute the Consulting Agreement attached hereto as Exhibit B that shall become effective on the Termination Date.

8. Miscellaneous Provisions.

(a) Waiver. No provision of this Agreement shall be modified, waived or discharged unless the modification, waiver or discharge is agreed to in writing and signed by Executive and

-3-

by an authorized officer of the Company. No waiver by either party of any breach of, or of compliance with, any condition or provision of this Agreement by the other party shall be considered a waiver of any other condition or provision or of the same condition or provision at another time.

(b) Non-Reliance. Executive acknowledges and agrees that in signing this Agreement, he does not rely and has not relied on any representation or statement by the Company or by its directors, officers, agents, representatives or attorneys with regard to the subject matter, basis or effect of this Agreement.

(c) Whole Agreement. No agreements, representations or understandings (whether oral or written and whether express or implied) which are not expressly set forth in this Agreement have been made or entered into by either party with respect to the subject matter hereof. Effective as of the date hereof, this Agreement supersedes any prior employment agreement or other Agreement between the Company, any of its subsidiary or parent entities and Executive, except that the Separation Agreement, Restricted Stock Unit Agreement, Option Agreement, Performance Option Agreement and Release, shall remain in force and effect in accordance with their respective terms, except as such terms are expressly modified, amended, terminated or released by this Agreement.

(d) No Admission of Wrongdoing. This Agreement is not an admission by the Company or Executive of any liability or wrongdoing.

(e) Choice of Law. This Agreement shall be deemed a contract made under, and for all purposes the validity, interpretation, construction and performance of this Agreement shall be governed by, the laws of the State of Delaware, without reference to principles of conflicts of laws, except to the extent superseded by applicable federal law.

(f) No Assignment. The rights of any person to payments or benefits under this Agreement shall not be made subject to option or assignment, either by voluntary or involuntary assignment or by operation of law, including (without limitation) bankruptcy, garnishment, attachment or other creditor’s process, and any action in violation of this Subsection (f) shall be void.

(g) Successors and Assigns. This Agreement will be binding upon and inure to the benefit of the Executive and his beneficiaries, heirs, executors, successors and assigns; and the Company, its affiliates, subsidiaries, successors and assigns.

(h) Confidentiality of Agreement. Executive agrees to keep strictly confidential the existence and terms of this Agreement and to not disclose them to any person or entity, other than to Executive’s immediate family, attorney, financial advisor, or except as required by law or except with respect to matters that have been publicly disclosed by the Company in filings with the Securities and Exchange Commission or otherwise publicly disclosed by the Company.

(i) Section 409A. This Agreement is intended to comply with the requirements of Section 409A of the Internal Revenue Code of 1986, as amended, and shall be interpreted accordingly.

-4-

IN WITNESS WHEREOF, each of the parties has executed this Agreement, in the case of the Company by its duly authorized representative, as of the day and year first above written.

PRIMUS TELECOMMUNICATIONS GROUP, INCORPORATED

-5-

EXHIBIT A

Release Agreement

This Release Agreement (the “Release Agreement”) is made this 29th day of March, 2010, by and between JOHN F. DEPODESTA (the “Executive”) and PRIMUS TELECOMMUNICATIONS GROUP, INCORPORATED and PRIMUS TELECOMMUNICATIONS, INC., both Delaware corporations (together, the “Company”)

Recitals:

Executive and the Company are parties to a Termination Agreement dated March 29, 2010 (the “Termination Agreement”) pursuant to which Executive is entitled to certain payments and benefits pursuant to Sections 2(a)(i),(ii) and (iii) of the Termination Agreement in consideration for granting a release of claims to the Company and the parties wish to state the terms of such release in this Release Agreement.

Now Therefore, for good and valuable consideration, the receipt and sufficiency of which are hereby acknowledged, Executive and the Company hereby agree as follows:

1. Release of Claims. In consideration for Executive’s right to receive the payments and benefits in the amount, manner and time of payment described in Sections 2(a)(i), (ii) and (iii) of the Termination Agreement, Executive hereby agrees to the following release of claims (the “Release”):

(a) Release. Executive, for himself and his heirs, executors and administrators, voluntarily, knowingly and willingly agrees to release the Company, together with its direct and indirect parents, subsidiaries, affiliates, predecessors and successors and assigns, past and present directors, managers, officers, executives, agents, clients, accountants, attorneys, and servants (collectively, the “Company Releasees”) from any and all claims, charges, complaints, promises, agreements, controversies, liens, demands, causes of action, obligations, damages, expenses (including attorneys’ fees and costs) and liabilities of any nature whatsoever (“Claims”), known or unknown, suspected or unsuspected, which Executive, or his heirs, executors or administrators ever had, now have, or may hereafter claim to have against any of the Company Releasees arising out of or relating to: (i) any matter, cause or thing whatsoever arising from the beginning of time to the date of this Release, (ii) Executive’s employment relationship with the Company or any of the Company Releasees or the separations thereof including, but not limited to, any such rights or claims arising under any statute or regulation including the Age Discrimination in Employment Act of 1967, Title VII of the Civil Rights Act of 1964, the Civil Rights Act of 1991, the Americans with Disabilities Act of 1990, the Family and Medical Leave Act of 1993, the Employee Retirement Income Security Act of 1974, the Delaware Equal Accommodations Law, the Virginia Human Rights Act, each as amended, or any other federal, state or local law, regulation, ordinance or common law, or (ii) any policy, agreement, understanding or promise,

-6-

written or oral, formal or informal, between Executive on the one hand and the Company or any of the Company Releasees on the other hand. Executive acknowledges that the amounts referred to in Section 2 of the Termination Agreement are in lieu of and in full satisfaction of any amounts that might otherwise be payable under any contract, agreement (oral or written), plan, policy or practice, past or present, of the Company or any of the Company Releasees; provided, however, that notwithstanding the foregoing, nothing contained in this Release shall in any way (i) diminish or impair any rights Executive may have, from and after the date the Release is executed, under the Separation Agreement dated July 1, 2009 (the “Separation Agreement”) between Executive and the Company or (ii) terminate, modify or release the rights that the Executive may have, from and after the date the Release is executed, under the Company’s Primary Directors & Officers Liability Policy (Policy Number: ELU112301-09), the Excess Directors & Officers Liability Policy (Policy Number HN-0303-2466), and the Run-Off Endorsement on Policy Number DO5N611527002, provided that the foregoing shall not preclude the amendment or termination of such policies from time to time in accordance with their respective terms (collectively, the “Excluded Claims”).

(b) Representations of Executive. Executive hereby makes the following representations and acknowledgements:

(i) Executive understands and agrees that, except for the Excluded Claims, he has knowingly relinquished, waived and forever released any and all rights to any personal recovery in any action or proceeding that may be commenced on Executive’s behalf arising out of the Claims that are released under the Release, including, without limitation, Claims for back pay, front pay, liquidated damages, compensatory damages, general damages, special damages, punitive damages, exemplary damages, costs, expenses and attorneys’ fees.

(ii) Executive represents that he has no claims, complaints, charges or lawsuits pending against the Company or any of the Company Releasees.

(iii) Executive acknowledges and agrees that he has had a sufficient period of time of up to 21 days within which to review the Termination Agreement and this Release, including, without limitation, with Executive’s attorney, and that Executive has done so to the extent desired.

(iv) Executive understands and agrees that the severance and benefits set forth in Section 2 of the Termination Agreement are the only consideration for the Executive’s signing the Release and no promise or inducement has been offered or made to induce the Executive to sign the Release, except as expressly set forth therein.

(v) Executive understands and agrees that the Release shall not become effective until the 8th day after the Executive signs this Release and the Executive may at any time before the effective date revoke the Release by hand delivering or sending via overnight mail a written notice of revocation to the Company: Primus Telecommunications Group, Incorporated, 7901 Jones Branch Drive, Suite 900, McLean, VA 22102, Attention: Chief Executive Officer. If Executive elects to revoke the Release as provided above, this Release Agreement and the Termination Agreement shall automatically terminate without liability or obligation to either party and the Separation Agreement shall remain in full force and effect without amendment or modification in accordance with its respective terms.

-7-

2. Choice of Law. This Agreement shall be deemed a contract made under, and for all purposes the validity, interpretation, construction and performance of this Agreement shall be governed by, the laws of the State of Delaware, without reference to principles of conflicts of laws, except to the extent superseded by applicable federal law.

3. Successors and Assigns. This Agreement will be binding upon and inure to the benefit of the Company Releases and their successors and assigns.

IN WITNESS WHEREOF, each of the parties has executed this Release Agreement, in the case of the Company by its duly authorized representative, as of the day and year first above written.

PRIMUS TELECOMMUNICATIONS GROUP, INCORPORATED

-8-