Exhibit 10.1

TERMINATION AGREEMENT

THIS TERMINATION AGREEMENT (the “Agreement”), entered into as of October 6, 2010, by and between K. PAUL SINGH (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 President and Chief Executive Officer;

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 August 31, 2010 (the “Termination Date”);

C. Executive and the Company and its subsidiary, Primus Telecommunications, Inc., are parties to an Executive Employment Agreement dated April 26, 2007 (the “Employment 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 terminated effective as of the Termination Date, and Executive and the Company agree that such termination shall be deemed to be without “Cause” (as defined under the Employment Agreement.

2. Payments to Executive. Provided that Executive executes the release of claims described in Section 3 of this Agreement and attached hereto as Exhibit A (the “Release Agreement”) and the Release Agreement is not revoked and becomes irrevocable, the Company shall make the following payments and provide the following additional compensation to Executive.

(a) On March 1, 2011, the Company shall pay to Executive, subject to Section 2(f) of this Agreement, $3,410,000, in a single lump sum, without interest.

(b) Upon the date on which the Release Agreement becomes irrevocable, the Company shall pay to Executive, subject to Section 2(f) of this Agreement: (i) $19,737.00 to reimburse Executive for medical and financial planning expenses incurred in 2009 and 2010 (but before September 1, 2010); (ii) $829.92 to reimburse Executive for business expenses submitted to the Company; and (iii) $41,442.69, which represents the value of Executive’s accrued but unused vacation as of the Termination Date.

(c) Restricted Stock Units. The Company and Executive hereby stipulate and agree that 114,928 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 Company equals or exceeds ninety percent (90%) of the Adjusted EBITDA Target for 2010 as set forth in the RSU Agreement, and as hereinafter modified, 76,619 additional RSUs will become vested. The remaining 38,309 unvested or contingent RSUs are hereby forfeited and terminated. Any additional vested RSUs will be settled on a one for one basis at the time provided in Section 3 of the RSU Agreement. Notwithstanding the provisions of Section 9(c) of this Agreement, the vested RSUs will remain subject to the terms of the RSU Agreement and the Company’s Management Compensation Plan. Notwithstanding the foregoing, however, for purposes of determining whether the Adjusted EBITDA Target has been satisfied, but solely for purposes of this Agreement, EBITDA shall be determined (i) without giving effect to any inorganic corporate events occurring after the Termination Date, and (ii) without regard to the payments made to Executive pursuant to Section 2(a) of this Agreement.

(d) Timed-Vested Non-Qualified Stock Options. The Company and Executive hereby stipulate and agree that 88,272 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 88,272 of such stock options under the Option Agreement are hereby forfeited and terminated. Notwithstanding the provisions of Section 9(c) of this Agreement, the vested Option shall remain subject to the terms of the Option Agreement and the Company’s Management Compensation Plan.

(e) Performance-Vested Non-Qualified Stock Option. The Company and the Executive hereby stipulate and agree that 28,732 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 Company equals or exceeds one hundred fifteen percent (115%) of the Adjusted EBITDA Target for 2010 as set forth in the Performance Option Agreement, and as hereinafter modified, options on 19,155 additional shares will become vested. The options on the remaining 9,577 shares are hereby forfeited and terminated. Notwithstanding the provisions of Section 9(c) of this Agreement, the vested options will remain subject to the terms of the Performance Option Agreement and the Company’s Management Compensation Plan. Notwithstanding the foregoing, however, for purposes of determining whether the Adjusted EBITDA Target has been satisfied, but solely for purposes of this Agreement, EBITDA shall be determined (i) without giving effect to any inorganic corporate events occurring after the Termination Date, and (ii) without regard to the payments made to Executive pursuant to Section 2(a) of this Agreement.

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

(g) No Additional Benefits. Executive acknowledges and agrees that the payments and other benefits provided for in this Agreement represent the only compensation and

- 2 -

benefits to which Executive is entitled and Executive is not entitled to any other compensation, remuneration, benefits or entitlements, whether pursuant to the Employment 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. Release. In consideration of the payments and mutual promises contained herein, Executive and the Company hereby execute the Release Agreement attached hereto as Exhibit A.

4. Resignation from Board of Directors. Executive hereby resigns, effective immediately, from all director and officer positions he holds with the Company and any of its affiliates and from which he has not previously resigned.

5. Restrictive Covenants. Notwithstanding the provisions of Section 9(c) of this Agreement, Executive hereby reaffirms and agrees that all of the terms, restrictions and covenants of Executive set forth in Sections 2.5, 2.6 and 2.7 of the Employment Agreement shall remain in full force and effect in accordance with their terms, without waiver, amendment, or release, provided, however, that nothing in Section 2.6 of the Employment Agreement shall be deemed to restrict Executive from any engaging in any of the following activities, subject to the provisions of Sections 2.5 and 2.7 of the Employment Agreement, at any time:

(a) Engaging or investing in the non-wholesale telecommunications business in countries other than the United States, Canada and Australia or Brazil; or

(b) Providing restructuring or business advisory services.

6. Return of Company Property. Executive acknowledges that all files, records, documents, computer disks, drawings, specifications, equipment, keys, credit cards and other property of the Company, including copies thereof, have been returned to the Company.

7. Cooperation in Litigation. The Executive agrees to reasonably 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.

8. 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.

- 3 -

9. 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 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.

(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 Commonwealth of Virginia, 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 through confidential due diligence investigations or 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.

- 4 -

(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.

(j) Attorneys’ Fees. The Company agrees to reimburse Executive for reasonable attorneys’ fees incurred by him in connection with this Agreement, such fees not to exceed $20,000.

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.

- 5 -

EXHIBIT A

RELEASE AGREEMENT

This Release Agreement (the “Release Agreement”) is made this      day of                 , 2010, by and between K. PAUL SINGH (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             , 2010 (the “Termination Agreement”) pursuant to which Executive is entitled to certain payments and benefits pursuant to 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. Executive 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 Section 2(a) of the Termination Agreement, Executive hereby agrees to the following release of claims (the “Executive Release”):

(a) Release by Executive. 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 (“Executive 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 Executive 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 (iii) any policy, agreement, understanding or promise, 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, provided, however, that notwithstanding the foregoing, nothing contained in this Executive Release shall in any way terminate, modify or release (1) Executive’s right to enforce the terms of this Release Agreement and the Termination Agreement, (2) the rights, if any, that the Executive may have, from and after the date the Executive Release is executed, under the Company’s Primary Directors & Officers Liability Policy, the Excess Directors & Officers Liability Policy, the Run-Off Endorsement or any other applicable D&O policy, provided that the foregoing shall not preclude the amendment or termination of such policies from time to time in accordance with their respective terms, provided any such amendment or termination applies equally to all former directors and officers of the Company and (3) any rights Executive may have to advancement or indemnification under the articles of incorporation or bylaws of the Company or any of its affiliates or under applicable law (collectively, the “Executive Excluded Claims”). 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.

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

(i) Executive understands and agrees that, except for the Executive 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 Executive Claims that are released under the Executive Release, including, without limitation, Executive 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 Executive 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 Executive Release and no promise or inducement has been offered or made to induce the Executive to sign the Executive Release, except as expressly set forth therein.

- ii -

(v) Executive understands and agrees that the Executive Release shall not become effective until the 8th day after the Executive signs this Executive Release and the Executive may at any time before the effective date revoke the Executive 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: General Counsel. If Executive elects to revoke the Executive Release as provided above, this Release Agreement and the Termination Agreement shall automatically terminate without liability or obligation to either party.

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 Commonwealth of Virginia, 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.

- iii -