Exhibit 99.1

FOR IMMEDIATE RELEASE

PAETEC Holding Corp. Announces First Quarter 2011 Results

FAIRPORT, N.Y. (May 5, 2011) – PAETEC Holding Corp. (NASDAQ GS: PAET) today announced first quarter 2011 operating results. “The integration of the 2010 acquisitions is progressing as evidenced by solid revenue growth and improved operating performance,” said Arunas A. Chesonis, chairman and CEO. “The combination of PAETEC’s deep product portfolio and the enhanced solutions acquired during 2010 showed tangible results during the first quarter.” Financial results for first quarter 2011 included the following:

1

First Quarter 2011 Results Compared to First Quarter 2010

Revenue

Adjusted EBITDA and Margins

Adjusted EBITDA for first quarter 2011 increased 39.4% or $25.8 million to $91.4 million over adjusted EBITDA of $65.5 million for first quarter 2010. Adjusted EBITDA margin, which represents adjusted EBITDA as a percentage of total revenue, improved 160 basis points to 18.4% from first quarter 2010. Operational expense synergies and improved network cost margins were the primary contributors to the improved adjusted EBITDA margin.

Cost of goods sold for first quarter 2011 increased 21.4% or $41.2 million. The increase in cost of goods sold for first quarter 2011 resulted from the Cavalier Telephone acquisition and the growth in the ISG product lines. Despite higher overall cost of goods sold, gross margin improved substantially by 220 basis points to 52.8% for first quarter 2011 from 50.6% for first quarter 2010. The improvement was driven by a broad array of operational enhancements including the contribution of higher margin Cavalier Telephone revenues, improved local network cost resulting

Free cash flow, as defined by PAETEC, consists of adjusted EBITDA less capital expenditures (purchases of property and equipment). See the accompanying tables for additional information as to PAETEC’s reasons for including these measures, for a quantitative reconciliation of adjusted EBITDA to net loss, as net loss is calculated in accordance with GAAP, and for a quantitative reconciliation of free cash flow to net cash provided by operating activities, as net cash provided by operating activities is calculated in accordance with GAAP.

2

from earlier initiatives to transition Special Access (“SPA”) circuits to Unbundled Network Elements (“UNE”), and stronger integrated equipment and network sales driven by the IP Simple Product, which leverages PAETEC’s proprietary Allworx platform.

Selling, general and administrative (“SG&A”) expenses for first quarter 2011 were $172.7 million, including stock-based compensation of $2.4 million, which represented an increase of $38.4 million over first quarter 2010 primarily due to the Cavalier Telephone acquisition. As a percentage of total revenue, SG&A expenses were 34.9% for first quarter 2011 compared to 34.4% for first quarter 2010.

Net Loss

Net loss for first quarter 2011 was $11.9 million compared to first quarter 2010 net loss of $9.5 million. The increase in net loss was primarily due to a 34.2% or $16.1 million increase in non-cash depreciation and amortization expense. Increased depreciation and amortization expense was driven by the acquired Cavalier Telephone assets, which included substantial fiber-optic infrastructure.

Sequential Results – First Quarter 2011 Compared to Fourth Quarter 2010

Revenue

Adjusted EBITDA and Margin

Adjusted EBITDA of $91.4 million for first quarter 2011 represented an increase of 26.7% or $19.3 million over adjusted EBITDA of $72.1 million for fourth quarter 2010. Adjusted EBITDA margin was 18.4% for first quarter 2011 compared to 16.8% for fourth quarter 2010. The strong margin improvement was a result of the impact of acquisition integration efforts as well as the inclusion of a full quarter of Cavalier Telephone revenue.

3

First quarter 2011 cost of goods sold increased 9.8% or $20.9 million from fourth quarter 2010, due to the inclusion of Cavalier Telephone’s results for a full quarter. Gross margin for first quarter 2011 was 52.8%, an increase from 50.4% for fourth quarter 2010. Cavalier Telephone integration efforts, network migration projects, and higher margin products all contributed to the solid improvement in overall gross margin.

SG&A expenses for first quarter 2011 were $172.7 million, including stock-based compensation of $2.4 million, and increased 18.2% or $26.6 million over fourth quarter 2010. The increase in SG&A was primarily attributable to the inclusion of a full quarter of Cavalier Telephone’s results. As a percentage of total revenue, SG&A expenses for first quarter 2011 increased to 34.9% from 34.0% for fourth quarter 2010. Higher benefits costs and seasonally higher payroll taxes resulted in a higher percentage of expenses on a sequential basis.

Net Loss

Net loss for first quarter 2011 was $11.9 million compared to net loss of $25.9 million for fourth quarter 2010. The reduction in net loss was primarily due to $13.4 million in non-recurring integration and transactional costs recorded for fourth quarter 2010 as compared to $2.5 million in similar costs recorded for first quarter 2011.

Actual First Quarter 2011 compared to Pro Forma First Quarter 2010

The following pro forma results for first quarter 2010 give effect to PAETEC’s acquisition of Cavalier Telephone as if it had occurred at the beginning of 2010. The pro forma information is not necessarily indicative of what the combined companies’ results of operations actually would have been if the acquisition had been completed as of the date indicated, nor of results that may be obtained in the future.

Actual total revenue of $495.5 million for first quarter 2011 represented an increase of 2.5% or $12.3 million over pro forma total revenue of $483.2 million for first quarter 2010. The increase in actual total revenue was primarily attributable to increased revenue from PAETEC’s acquisition of Quagga in June 2010 and U.S. Energy in February 2010. Actual adjusted EBITDA of $91.4 million for first quarter 2011 represented an increase of 3.6% or $3.2 million over pro forma adjusted EBITDA of $88.1 million for first quarter 2010.

4

Actual costs of goods sold for first quarter 2011 was stable at $233.9 million compared to pro forma first quarter 2010. For first quarter 2011, gross margins improved 100 basis points to 52.8% due to improved operating leverage associated with the transition from SPA circuits to UNE. Actual SG&A expenses as a percentage of actual total revenue increased to 34.9% for first quarter 2011 over pro forma SG&A expense as a percentage of pro forma revenue of 34.1% for first quarter 2010.

Actual net loss of $11.9 million for first quarter 2011 was unchanged compared to pro forma net loss from continuing operations for first quarter 2010.

Actual First Quarter 2011 Compared to Pro Forma Fourth Quarter 2010

The following pro forma results for fourth quarter 2010 give effect to PAETEC’s acquisition of Cavalier Telephone as if it had occurred at the beginning of 2010. The pro forma information is not necessarily indicative of what the combined companies’ results of operations actually would have been if the acquisition had been completed as of the date indicated, nor of results that may be obtained in the future.

Actual total revenue of $495.5 million for first quarter 2011 represented an increase of 0.5% or $2.2 million over pro forma total revenue of $493.3 million for fourth quarter 2010. The increase in actual total revenue was primarily attributable to organic growth in core network services revenue which more than offset seasonality in the ISG product lines. Actual adjusted EBITDA of $91.4 million for first quarter 2011 represented an increase of 4.4% or $3.8 million from pro forma adjusted EBITDA of $87.5 million for fourth quarter 2010.

Actual first quarter 2011 cost of goods sold was $233.9 million, a decrease of 2.7% or $6.4 million from pro forma cost of goods sold of $240.4 million for fourth quarter 2010. The decrease in costs was primarily due to improved network costs associated with the transition from SPA circuits to UNE. Actual gross margin increased 150 basis points to 52.8% for first quarter 2011 compared to pro forma gross margin of 51.3% for fourth quarter 2010. Actual SG&A expenses for first quarter 2011 were $172.7 million, an increase of 3.2% from pro forma SG&A expenses for fourth quarter 2010.

5

Actual net loss was $11.9 million for first quarter 2011 compared to pro forma net loss of $25.3 million for fourth quarter 2010. The decrease in actual net loss was primarily the result of lower additional acquisition and debt extinguishment costs, depreciation and amortization, and interest expense during the first quarter of 2011.

Capital Expenditures

For first quarter 2011, capital expenditures were $46.8 million, an increase of $17.4 million from first quarter 2010 primarily due to the acquisition of Cavalier Telephone. As a percentage of total revenue, capital expenditures were 9.5% for first quarter 2011 compared to 7.6% for first quarter 2010. The first quarter 2011 increase in capital expenditures was largely due to network enhancements to enable Ethernet over Copper, and investments in our fiber and data center infrastructure. Integration capital expenditures for first quarter 2011 were $1.5 million, and capital expenditures net of integration capital expenditures were 9.2% of first quarter 2011 revenues.

Cash Flow and Liquidity

PAETEC had a March 31, 2011 cash balance of $103.9 million compared to a year-end 2010 cash balance of $95.5 million, primarily as a result of cash generated by business operations.

Cash flow provided by operations increased to $60.7 million for first quarter 2011 from $7.8 million for first quarter 2010. Free cash flow for first quarter 2011 was $44.5 million, the 33rd consecutive quarter of free cash flow generation, and an $8.4 million increase from $36.1 million for first quarter 2010. Free cash flow for first quarter 2011 increased 6.2% from $41.9 million for fourth quarter 2010.

Indebtedness

At March 31, 2011, PAETEC had $1,400 million in debt outstanding under its senior notes, which was comprised of $650.0 million principal amount of senior secured notes and $750.0 million principal amount of senior unsecured notes.

PAETEC also had a senior secured revolving credit facility under which it could obtain from time to time revolving loans of up to an aggregate principal amount of $50.0 million. At March 31, 2011, $25.0 million principal amount of loans was outstanding under the facility.

6

Full Year 2011 Outlook

“We are pleased to reaffirm full year 2011 guidance,” said Keith Wilson, PAETEC’s chief financial officer.

PAETEC’s revenue and adjusted EBITDA expectations for full year 2011 assume, among other matters, that there is no further significant decline in economic conditions and that there are no significant changes in the competitive or regulatory environments. PAETEC’s revenue and adjusted EBITDA expectations for full year 2011 are as follows:

Conference Call

As previously announced, PAETEC will host a conference call today at 10:00 a.m. ET to discuss first quarter 2011 results. Chairman and CEO Arunas Chesonis and Chief Financial Officer Keith Wilson will be participating. A live webcast and a replay of the call will be available at www.paetec.com.

Conference Call details are as follows:

US/Canada Dial in: (866) 783-2142

International: (857) 350-1601

Passcode: 53440829

Audio Webcast:

http://phx.corporate-ir.net/phoenix.zhtml?p=irol-eventDetails&c=190031&eventID=3973549

Replay details are as follows:

Replay Dates: May 5, 2011, 1:00 p.m. ET through May 12, 2011

US/Canada Replay Dial in: (888) 286-8010

International Replay Dial in (617) 801-6888

Replay Passcode: 65832081

Audio Replay Webcast:

http://phx.corporate-ir.net/phoenix.zhtml?p=irol-eventDetails&c=190031&eventID=3973549

7

Supplemental Information

A supplemental presentation of information complementary to the information presented in this release and that will be discussed on the conference call will be made available on the Investor Relations portion of www.paetec.com prior to the conference call.

Forward-Looking Statements

Except for statements that present historical facts, this release contains “forward-looking statements” within the meaning of Section 27A of the Securities Act of 1933 and Section 21E of the Securities Exchange Act of 1934. In some cases, you can identify these statements by such forward-looking words as “anticipate,” “believe,” “could,” “estimate,” “expect,” “intend,” “may,” “plan,” “potential,” “should,” “will” and “would,” or similar expressions. Such forward-looking statements include the financial guidance in this press release with respect to revenue and adjusted EBITDA for full year 2011, which reflects PAETEC’s current analysis of existing trends and information. These statements represent PAETEC’s judgment only as of the date of this press release. Forward-looking statements involve known and unknown risks, uncertainties and other factors that may cause PAETEC’s actual operating results, financial position, levels of activity or performance to be materially different from those expressed or implied by such forward-looking statements. These risks include those related to the ability of PAETEC to consummate its previously announced acquisition of XETA Technologies and the ability of PAETEC to integrate the operations of XETA without greater than expected costs and burdens on management. Some of the other risks, uncertainties and factors are discussed under the caption “Risk Factors” in PAETEC’s 2010 Annual Report on Form 10-K and in PAETEC’s subsequently filed SEC reports. They include, but are not limited to, the following risks, uncertainties and other factors: general economic conditions and trends; the continued availability of necessary network elements at acceptable cost from competitors; changes in regulation and the regulatory environment; industry consolidation; PAETEC’s ability to manage its business effectively; competition in the markets in which PAETEC operates; failure to adapt product and service offerings to changes in customer preferences and in technology; PAETEC’s ability to integrate the operations of acquired businesses; PAETEC’s ability to implement its acquisition strategy; any significant impairment of PAETEC’s goodwill; future sales of PAETEC’s common stock in the public market and PAETEC’s ability to raise capital in the future; PAETEC’s significant level of debt and interest payment obligations and compliance with covenants under PAETEC’s debt agreements; PAETEC’s ability to attract and retain qualified personnel and sales agents; PAETEC’s failure to obtain and maintain network permits and rights-of-way; PAETEC’s

8

involvement in disputes and legal proceedings; PAETEC’s ability to maintain and enhance its back office systems; and effects of network failures, system breaches, natural catastrophes and other service interruptions. PAETEC disclaims any obligation to update any forward-looking statements, whether as a result of new information, future events or otherwise.

About PAETEC

PAETEC (NASDAQ GS: PAET) is personalizing business communications for medium-sized and large businesses, enterprise organizations, and institutions across the United States. We offer a comprehensive suite of IP, voice, data and Internet services, as well as enterprise communications management software, network security solutions, CPE, and managed services. For more information, visit www.paetec.com.

9

PAETEC Holding Corp. and Subsidiaries

Consolidated Statements of Operations

(in thousands)

PAETEC Holding Corp. and Subsidiaries

Adjusted EBITDA Reconciliation

(in thousands)

Adjusted EBITDA, as defined by PAETEC for the periods presented, represents net loss before depreciation and amortization, interest expense, provision for (benefit from) income taxes, stock-based compensation, acquisition, integration and separation costs, and debt extinguishment and related costs. PAETEC’s adjusted EBITDA is not a financial measurement prepared in accordance with United States generally accepted accounting principles, or “GAAP.” Adjusted EBITDA is used by PAETEC’s management, together with financial measurements prepared in accordance with GAAP such as net loss and revenue, to assess PAETEC’s historical and prospective operating performance. Management uses adjusted EBITDA to enhance its understanding of PAETEC’s core operating performance, which represents management’s views concerning PAETEC’s performance in the ordinary, ongoing and customary course of its operations. See “Management’s Discussion and Analysis of Financial Condition and Results of Operations — Overview — Adjusted EBITDA Presentation” in PAETEC’s annual report on Form 10-K for the year ended December 31, 2010 for additional information regarding PAETEC’s reasons for including adjusted EBITDA and for material limitations with respect to the usefulness of this measurement. The table below sets forth, for the periods indicated, a reconciliation of adjusted EBITDA to net loss, as net loss is calculated in accordance with GAAP:

PAETEC Holding Corp. and Subsidiaries

Expected Adjusted EBITDA Reconciliation

(in millions)

The table below sets forth, for the period indicated, a reconciliation of expected adjusted EBITDA to expected net loss, as net loss is calculated in accordance with GAAP:

PAETEC Holding Corp. and Subsidiaries

Free Cash Flow Calculation and Reconciliation

(in thousands)

Free cash flow, as defined by PAETEC, consists of adjusted EBITDA less capital expenditures (purchases of property and equipment). Free cash flow, as defined by PAETEC, is not a financial measurement prepared in accordance with GAAP.

PAETEC has included data with respect to free cash flow because its management believes free cash flow provides a measure of the cash generated by PAETEC’s operations before giving effect to non-cash accounting charges, changes in operating assets and liabilities, acquisition-related items, tax items and similar items that do not directly relate to the day-to-day cash expenses of PAETEC’s operations, and after giving effect to application of capital expenditures. PAETEC’s management uses free cash flow to monitor the effect of PAETEC’s daily operations on its cash reserves and its ability to generate sufficient cash flow to fund PAETEC’s scheduled debt maturities and other financing activities, including potential refinancings and retirements of debt, and other cash items.

PAETEC’s management believes that consideration of free cash flow should be supplemental, however, because free cash flow has limitations as an analytical financial measure. These limitations include the following:

PAETEC’s management compensates for these limitations by relying primarily on PAETEC’s results under GAAP to evaluate its operating performance and by considering independently the economic effects of the foregoing items that are not reflected in free cash flow. As a result of these limitations, free cash flow should not be considered as an alternative to net cash provided by operating activities, investing activities, financing activities or changes in cash and cash equivalents as calculated in accordance with GAAP, nor should it be used as a measure of the amount of cash available for debt service or for the payment of dividends or other discretionary expenditures.

Following is a reconciliation of free cash flow to net cash provided by operating activities, as net cash provided by operating activities is calculated in accordance with GAAP:

PAETEC Holding Corp. and Subsidiaries

Selected Financial and Operating Data

PAETEC Holding Corp. and Subsidiaries

Pro Forma Condensed Consolidated Statements of Operations

(in thousands)

The following pro forma results for the periods ended December 31, 2010 and March 31, 2010 give effect to PAETEC’s acquisition of Cavalier as if it had occurred on January 1, 2010. The pro forma information is not necessarily indicative of what the combined companies’ results of operations actually would have been if the merger had been completed on the date indicated. For comparision purposes, PAETEC’s actual results for the three month period ended March 31, 2011 also are presented.

PAETEC Holding Corp. and Subsidiaries

Pro Forma Adjusted EBITDA Reconciliation

(in thousands)

Pro forma adjusted EBITDA, as defined by PAETEC for the periods presented, represents pro forma net loss from continuing operations before depreciation and amortization, interest expense, provision for (benefit from) income taxes, stock-based compensation, acquisition, integration and separation costs, and debt extinguishment and related costs. The table below sets forth, for the three months ended March 31, 2010 and December 31, 2010, a reconciliation of pro forma adjusted EBITDA to pro forma net loss from continuing operations, as pro forma net loss from continuing operations is calculated in accordance with GAAP. For comparision purposes, a reconciliation of actual adjusted EBITDA to actual net loss, for the three months ended March 31, 2011, also is presented.