NOTE EXCHANGE AGREEMENT

Exhibit 10.1

NOTE EXCHANGE AGREEMENT

NOTE EXCHANGE AGREEMENT, dated as of December 19, 2012 (this “Agreement”), by and among Primus Telecommunications Holding, Inc. (the “Company”) and each of the parties listed on the signature pages hereto (each a “Noteholder”, and collectively, the “Noteholders”). Capitalized terms used herein and not otherwise defined shall have the meanings ascribed to such terms in the Indenture (as defined herein).

WHEREAS, the Company has previously issued its 10% Senior Secured Notes due 2017 (the “10% Notes”) pursuant to the Indenture, dated as of July 7, 2011, among the Company, the Guarantors and U.S. Bank National Association, as Trustee and as Collateral Agent (the “Trustee”), as amended by the First Supplemental Indenture, dated as of September 17, 2012, by and among the Company, the Guarantors and the Trustee, and as further amended by the Second Supplemental Indenture, dated as of November 14, 2012, by and among the Company, the Guarantors and the Trustee (as so amended, the “Indenture”);

WHEREAS, the Indenture authorizes the issuance by the Company of 10.00% Senior Secured Exchange Notes due 2017 (the “10% Exchange Notes”), which 10% Exchange Notes are substantially identical to the 10% Notes, except that the 10% Exchange Notes shall at all times be redeemable at the option of the Company at a redemption price equal to 100% of the principal amount thereof plus accrued and unpaid interest thereon to the date of redemption;

WHEREAS, each Noteholder beneficially owns the aggregate principal amount of 10% Notes set forth in the written instrument executed by such Noteholder and delivered to the Company contemporaneously with the execution and delivery of this Agreement (each such instrument, a “Noteholder Letter” and with the 10% Notes referenced in the Noteholder Letter being referred to herein as such Noteholder’s “Subject Notes”); and

WHEREAS, contemporaneously with the execution and delivery of this Agreement, each of the Noteholders will exchange its 10% Notes for 10% Exchange Notes, and the Company will issue such 10% Exchange Notes in exchange, at a rate, expressed in principal amount of 10% Exchange Notes (the “Exchange Rate”), equal to (x) $1.09 minus (y) the amount of interest accrued on each $1.00 principal amount of 10% Notes for the period from November 14, 2012 to, but not including, the date hereof, such amount to be rounded to the nearest one-tenth of one cent, for each $1.00 principal amount of 10% Notes so exchanged, and otherwise in accordance with the terms and conditions of this Agreement (the “Note Exchange”).

NOW, THEREFORE, in consideration of the premises and the representations, warranties and agreements contained herein, the parties hereto agree as follows:

1. Note Exchange. Contemporaneously with the execution and delivery of this Agreement, the parties shall effectuate the Note Exchange in the following manner: (a) the Company shall issue and deliver to the Trustee, and shall cause the Trustee to authenticate and deliver and hold as custodian for The Depository Trust Company, to be credited to the accounts of the Noteholders specified in the applicable Noteholder Letters, an aggregate principal amount of 10% Exchange Notes equal to the aggregate principal amount of the Subject Notes exchanged hereunder multiplied by the Exchange Rate and (b) the Noteholders severally (and not jointly) shall deliver to the Company all of their respective Subject Notes (the “Exchanged 10% Notes”)

by causing their DTC participants to effect a deposit/withdrawal at custodian of the Exchanged 10% Notes to the Trustee. In addition, the Company shall pay to each Noteholder an amount in cash, by wire transfer of immediately available funds, equal to (x) the accrued but unpaid interest on such Noteholder’s Exchanged 10% Notes for the period from October 15, 2012 to, but not including, November 14, 2012. The 10% Exchange Notes issued pursuant to the Note Exchange shall accrue interest from November 14, 2012.

2. Representations and Warranties of the Company. The Company represents and warrants to the Noteholders effective as of the date hereof as follows:

(a) Due Organization. The Company is duly organized, validly existing and in good standing under the laws of the jurisdiction of its organization.

(b) Due Authorization; Binding Agreement; No Conflicts. The Company has full right, power and authority to execute and deliver this Agreement and to consummate the transactions contemplated hereby. This Agreement has been duly and validly authorized, executed and delivered by the Company and (assuming due authorization, execution and delivery by the Noteholders) constitutes the valid and binding obligation of the Company enforceable against the Company in accordance with its terms, subject to the effects of bankruptcy, insolvency, fraudulent conveyance, reorganization, moratorium and other similar laws relating to or affecting creditors’ rights generally, and general equitable principles (whether considered in a proceeding in equity or at law). Neither this Agreement nor the consummation of the Note Exchange will violate, conflict with or result in a breach of or default under (i) the certificate of incorporation or bylaws of the Company, (ii) any agreement or instrument to which the Company is a party or by which the Company or any of its assets are bound, or (iii) any laws, regulations or governmental or judicial decrees, injunctions or orders applicable to the Company.

(c) Validity of 10% Exchange Notes. The 10% Exchange Notes issued pursuant to this Agreement, when authenticated by the Trustee and delivered in exchange for the Exchanged 10% Notes in accordance with this Agreement, will be the valid and binding obligations of the Company enforceable against the Company in accordance with their terms, subject to the effects of bankruptcy, insolvency, fraudulent conveyance, reorganization, moratorium and other similar laws relating to or affecting creditors’ rights generally, and general equitable principles (whether considered in a proceeding in equity or at law).

3. Representations and Warranties of the Noteholders. Each Noteholder hereby, severally and not jointly, represents and warrants to the Company as of the date hereof as follows:

(a) Due Organization. Such Noteholder is duly organized and validly existing under the laws of the jurisdiction of its organization.

(b) Due Authorization; Binding Agreement. Such Noteholder has full right, power and authority to execute and deliver this Agreement and to consummate the transactions contemplated hereby. This Agreement has been duly and validly authorized, executed and

2

delivered by such Noteholder and (assuming due authorization, execution and delivery by the Company) constitutes the valid and binding obligation of such Noteholder enforceable against such Noteholder in accordance with its terms, subject to the effects of bankruptcy, insolvency, fraudulent conveyance, reorganization, moratorium and other similar laws relating to or affecting creditors’ rights generally, and general equitable principles (whether considered in a proceeding in equity or at law).

(c) Ownership of the Subject Notes. Such Noteholder is, and at all times since November 14, 2012 has been, the beneficial owner of all of its Subject Notes, free and clear of any adverse claim, mortgage, pledge, lien, encumbrance, option, charge or other security interest that would prevent such Noteholder’s compliance with its obligations hereunder. Such Noteholder does not own, beneficially or of record, any 10% Notes of the Company or securities convertible or exchangeable for 10% Notes of the Company other than as set forth in the applicable Noteholder Letter. Such Noteholder has the sole right and power to vote and dispose of the Subject Notes, and none of such Subject Notes is subject to any voting trust or other agreement, arrangement or restriction with respect to the voting or transfer of any of the Subject Notes, except for this Agreement.

(d) Investment Intent. The 10% Exchange Notes to be acquired by such Noteholder pursuant to this Agreement shall be acquired for such Noteholder’s own account and not with a view to, or intention of, distribution thereof in violation of the Securities Act of 1933, as amended (the “Securities Act”), or any applicable state securities laws, and such 10% Exchange Notes shall not be disposed of in contravention of the Securities Act or any applicable state securities laws.

(e) Sophisticated Investor. Such Noteholder is a “qualified institutional buyer” as defined in Rule 144A under the Securities Act or an “accredited investor” or “institutional accredited investor” as defined in Rule 501 under Regulation D of the Securities Act. Such Noteholder is able to bear the economic risk of its investment in the 10% Exchange Notes for an indefinite period of time and acknowledges that no public market exists for the 10% Exchange Notes and that there is no assurance that a public market will ever develop for the 10% Exchange Notes. The 10% Exchange Notes have not been registered under the Securities Act and, therefore, cannot be sold unless subsequently registered under the Securities Act or an exemption from such registration is available. Such Noteholder understands that the tax consequences of the Note Exchange are complex, and accordingly such Noteholder represents and warrants that it has consulted with its own independent tax advisor concerning the Note Exchange and is not relying on the Company or any of its respective affiliates or agents, including its counsel and accountants, for any tax advice regarding the tax consequences of the Note Exchange or any other transactions contemplated by this Agreement.

(f) Information. Such Noteholder has reviewed, or has had the opportunity to review, with the assistance of professional and legal advisors of its choosing, sufficient information (including all documents filed or furnished to the Securities and Exchange Commission by Primus Telecommunications Group, Incorporated) and has had sufficient access to the Company necessary for such Noteholder to decide to exchange its 10% Notes for 10% Exchange Notes in accordance with this Agreement.

3

4. General Provisions.

(a) Closing. The closing of the transactions contemplated by this Agreement shall occur simultaneously with the execution and delivery of this Agreement.

(b) Amendments, Etc. No amendment, modification, termination, or waiver of any provision of this Agreement, and no consent to any departure by any of the Noteholders or the Company from any provision of this Agreement, shall be effective unless it shall be in writing and signed and delivered by the party sought to be bound, and then it shall be effective only in the specific instance and for the specific purpose for which it is given.

(c) Disclosure. Nothing contained in this Agreement shall be construed to limit the Company or any Noteholder from making such disclosures as may be required by law.

(d) Notice. All notices and other communications hereunder shall be in writing and shall be deemed given if delivered personally, telecopied (with confirmation), mailed by registered or certified mail (return receipt requested) or delivered by an express courier (with confirmation) to the Company at 7901 Jones Branch Drive, Suite 900, McLean, Virginia 22102, Attention: General Counsel, Facsimile: (703)  ###-###-####, and to each Noteholder at the address set forth in the applicable Noteholder Letter (or at such other address for a party as shall be specified by like notice).

(e) Severability. Any term or provision of this Agreement which is invalid or unenforceable in any jurisdiction shall, as to that jurisdiction, be ineffective to the extent of such invalidity or unenforceability without rendering invalid or unenforceable the remaining terms and provisions of this Agreement or affecting the validity or enforceability of any of the terms or provisions of this Agreement in any other jurisdiction.

(f) Governing Law. This Agreement shall be governed by, and construed in accordance with, the laws of the State of New York.

(g) Entire Agreement. This Agreement embodies the entire agreement and understanding of the Noteholders and the Company with respect to the subject matter hereof and thereof, and supersedes all prior agreements or understandings, with respect to the subject matter of this Agreement.

(h) Specific Performance; Enforcement. Each of the parties hereto recognizes and acknowledges that a breach by it of any covenants or agreements contained in this Agreement will cause the other party to sustain damages for which it would not have an adequate remedy at law for money damages, and therefore, each of the parties hereto agrees that in the event of any such breach the aggrieved party shall be entitled to the remedy of specific performance of such covenants and agreements and injunctive and other equitable relief in addition to any other remedy to which it may be entitled at law or in equity. The parties agree that they shall be entitled to enforce specifically the terms and provisions of this Agreement in addition to any other remedy to which they may entitled at law or in equity. In addition, each of the parties hereto (i) agrees that any action related to or arising

4

out of this Agreement or any of the transactions contemplated hereby shall be brought in the Court of Chancery of the State of Delaware, unless the Court of Chancery of the State of Delaware does not have subject matter jurisdiction over the action, in which case, any action related to or arising out of this Agreement or any of the transactions contemplated hereby shall be brought in the Superior Court of the State of Delaware or the United States District Court for the District of Delaware, (ii) consents to the personal jurisdiction of each of the courts listed in subsection (i) hereof in the event any action related to or arising out of this Agreement or any of the transactions contemplated hereby is brought, (iii) agrees that such party will not attempt to deny or defeat such personal jurisdiction by motion or other request for leave from any such court, (iv) consents to service of process in the manner set forth in paragraph 4(d) of this Agreement in connection with any action related to or arising out of this Agreement or any of the transactions contemplated hereby and (v) waives any right to trial by jury in any action related to or arising out of this Agreement or any of the transactions contemplated hereby.

(i) Counterparts; Facsimile. This Agreement may be executed in counterparts, all of which shall be considered one and the same agreement, and shall become effective when counterparts have been signed by each of the parties and delivered to the other parties, it being understood that all parties need not sign the same counterpart. This Agreement may be executed by facsimile signatures of the parties hereto.

(j) Expenses. All fees and expenses with respect to the negotiation of this Agreement and the consummation of the transactions contemplated hereby shall be borne by the party incurring such fees and expenses.

[Signature page follows]

5

IN WITNESS WHEREOF, the Company, each Guarantor and each Noteholder has caused this Agreement to be executed on its behalf as of the date first written above.

NOTEHOLDERS: