Exhibit 99.1

Primus Telecommunications Group, Incorporated

Reports First Quarter 2011 Results

MCLEAN, VA – (MARKET WIRE) – May 16, 2011 – Primus Telecommunications Group, Incorporated (PTGi) (OTCBB: PMUG), a global facilities-based integrated provider of advanced telecommunications products and services, announced results for the first quarter ended March 31, 2011. PTGi completed the acquisition of Arbinet Corporation on February 28, 2011; therefore, first quarter 2011 comparisons are not directly comparable with prior periods.

Consolidated Results

Net revenue for the first quarter 2011 was $223.7 million, an increase of 15.9% from first quarter 2010 net revenue of $193.0 million. Net revenue includes a $26.8 million contribution from Arbinet. Adjusted EBITDA was $18.6 million, a decrease of 11.4% from first quarter 2010 Adjusted EBITDA of $21.0 million. Adjusted EBITDA includes $0.2 million of loss from Arbinet after excluding $1.3 million of severance and integration costs. The impact of foreign exchange translation was a positive $13.1 million to revenue for the first quarter 2011 and a positive $1.6 million to Adjusted EBITDA. Free cash flow decreased in the quarter to $9.6 million from first quarter 2010 free cash flow of $12.8 million.

Peter D. Aquino, Chairman, President and Chief Executive Officer, stated, “PTGi advanced all of our strategic objectives during the first quarter of 2011. We closed the Arbinet acquisition in February and are now executing our integration plan to achieve $3 million and $7 million of synergies in 2011 and 2012, respectively. We continue to keep an eye out for opportunistic tuck-ins that can increase our scale or enhance the services set that PTGi delivers to customers. We also launched key initiatives in Canada and Australia designed both to improve our operations and to capture data center and metro fiber growth opportunities in our commercial businesses. Lastly, in April we reduced our debt load by $24.0 million and have reached an agreement with a majority of our holders of our 13% Senior Secured Notes to re-launch our debt exchange in the coming weeks. Our new exchange offer is designed to substantially reduce interest expense and improve free cash flow. With this balance sheet strengthening in progress, we remain focused on making further operational and financial advances for the new PTGi.”

Key First Quarter 2011 Accomplishments

First Quarter 2011 Net Revenue by Major Operating Segment

Canada – Net revenue of $60.8 million increased 5.8% from $57.5 million in the first quarter 2010. The impact of foreign currency translation was a positive $3.2 million. On a constant currency basis, net revenue was flat as declines in residential long distance and prepaid cards were offset by increases in residential local, data centers and SME VoIP.

Australia – Net revenue of $71.7 million increased 2.6% from $69.9 million in first quarter 2010. The impact of foreign currency translation was a positive $7.3 million. On a constant currency basis, net revenue decreased 7.8% as declines in residential local and dial-up revenues were partially offset by growth in data center and local on-net revenues.

International Carrier Services – Net revenue of $73.0 million increased 57.0% from $46.5 million in first quarter 2010, primarily due to including one month of Arbinet net revenue of $26.8 million. The impact of foreign currency translation was a positive $2.1 million. On a constant currency basis, net revenue increased 52.6%; excluding Arbinet, ICS revenue decreased slightly as the Company targeted higher margin traffic with lower volume.

United States – Net revenue of $11.2 million decreased 19.3% from $13.9 million in first quarter 2010, primarily due to decreases in retail voice services and consumer VoIP.

Other Businesses –

Brazil – Net revenue of $6.8 million increased 28.5% from $5.3 million in first quarter 2010. The impact of foreign currency translation was a positive $0.5 million. On a constant currency basis, net revenue increased 18.6% due primarily to growth in data center/hosting services and wholesale voice revenue. As part of its asset portfolio review, PTGi continues to explore strategic alternatives for Brazil.

Further First Quarter 2011 Detail

Net revenue less cost of revenue was $71.5 million, or 31.9% of net revenue, compared to $71.0 million, or 36.8% of net revenue, in first quarter 2010. Net revenue less cost of revenue, as a percentage of net revenue, was negatively impacted by the addition of lower margin Arbinet customers.

Selling, general and administrative (SG&A) expense was $54.0 million, or 24.1% of net revenue, in the first quarter 2011 compared to $50.1 million, or 26.0% of net revenue in first quarter 2010. Included in first quarter 2011 SG&A were severance and integration costs of $1.7 million and $1.8 million of other SG&A expense from Arbinet.

Income (loss) from operations was a loss of $12.3 million compared to income of $3.0 million in the first quarter 2010. The first quarter of 2011 includes a $14.7 million impairment charge to goodwill related to the Arbinet acquisition. The allocation of the purchase price is subject to additional adjustment until the Company has completed its valuation of Arbinet’s assets and liabilities. The total consideration allocated to the assets acquired and liabilities assumed increased from the date of the merger agreement (November 10, 2010) to the closing date (February 28, 2011) as the result of a significant increase in PTGi’s stock price. Depreciation and amortization expense was $15.1 million as compared to $17.9 million in first quarter 2010. This reduction is due to fully depreciating and amortizing fixed assets and customer lists that were re-valued as part of fresh start accounting upon emergence from bankruptcy. It is expected that depreciation and amortization expense related to the pre-bankruptcy assets will continue to run off at an accelerated pace over the next two years.

Adjusted EBITDA was $18.6 million, or 8.3% of net revenue, compared to $21.0 million, or 10.9% of net revenue, in the first quarter 2010. First quarter 2011 Adjusted EBITDA excluding severance and integration costs was $20.3 million.

Net loss was $19.3 million, or $(1.73) per basic and diluted common share, compared to $1.0 million, or $(0.10) per basic and diluted common share in the first quarter 2010.

The number of shares outstanding used to calculate basic and diluted earnings per common share in the first quarter of 2011 was 11.1 million compared to 9.6 million for basic and diluted earnings per common share in the first quarter 2010.

Balance Sheet, Liquidity and Capital Resources

PTGi ended the first quarter 2011 with $65.7 million in unrestricted cash and cash equivalents, up from $41.5 million at December 31, 2010. Cash was generated during the quarter in the following amounts: $18.6 million of Adjusted EBITDA, $14.1 million of cash and marketable securities acquired from business acquisitions, net of cash paid, and $2.0 million of working capital, offset by the usage of $6.4 million for capital expenditures and $4.1 million for severance paid.

The principal amount of PTGi’s long-term obligations as of March 31, 2011 was $245.6 million, down from $245.7 million as of December 31, 2010. Subsequent to quarter-end, PTGi used $25.3 million of cash to redeem a portion of its 14.25% Senior Subordinated Secured Notes, which included $1.3 million of accrued interest.

Free Cash Flow in the first quarter 2011 was $9.6 million compared to free cash flow of $12.8 million in the first quarter 2010. Severance costs paid and higher capital expenditures were primary contributors to the decrease in free cash flow over the prior year quarter. PTGi defines Free Cash Flow as net cash provided by operating activities less cash used in the purchase of property and equipment.

James C. Keeley, Interim Chief Financial Officer, stated, “First quarter 2011 results reflect the inclusion of Arbinet in March, which had minimal effect to Adjusted EBITDA excluding severance and integration charges, and offers us tremendous scale and synergy opportunities. Free Cash Flow was $9.6 million, and we ended the quarter with over $65 million of cash, partially due to the inclusion of Arbinet’s cash, giving us confidence to redeem a portion of our 14.25% Senior Subordinated Secured Notes. We remain committed to further improving operating profitability, transforming our balance sheet, and driving positive Free Cash Flow.”

Conference Call

The Company will hold a conference call and webcast on May 17, 2011 at 8:30 AM ET. To access the call, please dial 866-305-6438 (toll free) or 706-679-7161 approximately 10 minutes prior to the start of the conference call. The conference call will also be broadcast live over the Internet with an accompanying slide presentation, which can be accessed via the Investor Relations section of PTGi’s web site at www.ptgi.com. The webcast and slide presentation will be available for replay for 90 days at www.ptgi.com.

A telephonic replay of this conference call will also be available by dialing 800-642-1687 (toll free) or 706-645-9291 (access code: 64864630) from 12:30 PM ET on May 17, 2011 until midnight ET on May 24, 2011.

About PTGi

PTGi is a leading provider of advanced communication solutions, including, traditional and IP voice, data, mobile services, broadband Internet, collocation, hosting, and outsourced managed services to business and residential customers in the United States, Canada, Australia, and Brazil. PTGi is also one of the leading international wholesale service providers to fixed and mobile network operators worldwide. PTGi owns and operates its own global network of next-generation IP soft switches, media gateways, hosted IP/SIP platforms, broadband infrastructure, fiber capacity, and data centres located in Canada, Australia, and Brazil. Founded in 1994, PTGi is headquartered in McLean, Virginia. For more information, visit http://www.ptgi.com.

Non-GAAP Financial Measures

This release includes certain non-GAAP financial measures as defined under SEC rules, which include Adjusted EBITDA and Free Cash Flow. PTGi has provided a reconciliation of these measures to the most directly comparable GAAP measures, which is contained in the tables to this release. Additionally, information regarding the purpose and use for these non-GAAP financial measures is set forth in our Form 8-K disclosing this press release.

Cautionary Statement Regarding Forward-Looking Statements

This document and related verbal statements include “forward-looking statements” as defined by the Securities and Exchange Commission, and include without limitation statements regarding Arbinet acquisition integration

efforts, Arbinet scale and synergy opportunities, and our debt reduction, exchange offer, refinancing and capital objectives. All statements, other than statements of historical fact, included herein that address activities, events or developments that PTGi expects, believes or anticipates will or may occur in the future are forward-looking statements. These forward-looking statements are subject to risks and uncertainties that may cause actual results to differ materially. In some cases, you can identify forward-looking statements by terminology such as “if,” “may,” “should,” “believe,” “anticipate,” “future,” “forward,” “potential,” “estimate,” “reinstate,” “opportunity,” “goal,” “objective,” “exchange,” “growth,” “outcome,” “could,” “expect,” “intend,” “plan,” “strategy,” “provide,” “commitment,” “result,” “seek,” “pursue,” “ongoing,” “include” or the negative of such terms or comparable terminology. Risks and uncertainties that could affect forward-looking statements include, but are not limited to, the following: the possibility that the expected synergies from the merger with Arbinet will not be realized, or will not be realized within the anticipated time period; the risk that PTGi’s and Arbinet’s businesses will not be integrated successfully; the possibility of disruption from the Arbinet merger making it more difficult to maintain business and operational relationships; the ability to service substantial indebtedness; and the risk factors or uncertainties described from time to time in PTGi’s filings with the Securities and Exchange Commission (including, among others, those listed under captions titled “Management’s Discussion and Analysis of Financial Condition and Results of Operations — Liquidity and Capital Resources — Short- and Long-Term Liquidity Considerations and Risks;” “— Special Note Regarding Forward-Looking Statements;” and “Risk Factors” in PTGi’s annual report on Form 10-K and quarterly reports on Form 10-Q that cover matters and risks including, but not limited to: (a) a continuation or worsening of global recessionary economic conditions, including the effects of such conditions on our customers and our accounts receivables and revenues; (b) the general fluctuations in the exchange rates of currencies, particularly any strengthening of the United States dollar relative to foreign currencies of the countries where we conduct our foreign operations; (c) the possible inability to raise additional capital or refinance indebtedness when needed, or at all, whether due to adverse credit market conditions, our credit profile or otherwise; (d) a continuation or worsening of turbulent or weak financial and capital market conditions; (e) adverse regulatory rulings or changes in the regulatory schemes or requirements and regulatory enforcement in the markets in which we operate and uncertainty regarding the nature and degree of regulation relating to certain services; and (f) successful implementation of cost reduction efforts. Readers are cautioned not to place undue reliance on forward-looking statements, which speak only as of their dates. PTGi undertakes no obligation to update or revise its forward-looking statements, whether as a result of new information, future events or otherwise.

Investor Contact:

PTGi

Richard Ramlall, SVP Corporate Development and Chief Communications Officer

703-748-8050

ir@ptgi.com

Lippert/Heilshorn & Assoc., Inc.

Carolyn Capaccio

212-838-3777

ccapaccio@lhai.com

(tables follow)

PRIMUS TELECOMMUNICATIONS GROUP, INCORPORATED

CONDENSED CONSOLIDATED STATEMENTS OF OPERATIONS

(in thousands, except per share amounts)

PRIMUS TELECOMMUNICATIONS GROUP, INCORPORATED

CONDENSED CONSOLIDATED BALANCE SHEET

(in thousands)

(unaudited)

PRIMUS TELECOMMUNICATIONS GROUP, INCORPORATED

RECONCILIATION OF NET INCOME TO ADJUSTED EBITDA

(in thousands)

(unaudited)

PRIMUS TELECOMMUNICATIONS GROUP, INCORPORATED

RECONCILIATION OF NET CASH PROVIDED BY (USED IN) OPERATING ACTIVITIES

TO FREE CASH FLOW

(in thousands)

(unaudited)

# # #