• New Installs of 21,800 Lines; 83% Were "On-Switch"
• Total Lines in Service Increases to 47,700
• 50 New Collocations for a Total of 101
• 3 New Markets in Service for a Total of 9
• 91% of New Lines Sold Were "On-Switch"
• Sales Run Rate of 86,500 Lines--Annualized Revenue Run Rate in Excess of $50 Million
• Introduction of First Phase of Internet Communications Services
• Implementation of Electronic Bonding with Bell Atlantic

DALLAS, TEXAS, February 4, 1999 - Allegiance Telecom, Inc. (Nasdaq: ALGX), a competitive local exchange carrier (CLEC), today announced results for its fourth quarter. Allegiance reported fourth quarter revenues of $5.6 million, an increase of 100% over 3Q98 revenues of $2.8 million. Lines sold as well as lines installed continued to exceed plan, with new lines sold increasing from 22,300 in 3Q98 to 43,100 lines in 4Q98- 91% of the new lines sold were "on-switch." Lines installed also showed rapid growth, with new lines installed increasing from 14,900 in 3Q98 to 21,800 in 4Q98-83% of the new installs were "on-switch." Bookings through December 1998 resulted in an annualized recurring revenue run rate in excess of $50 million.

"During the year, we demonstrated that we can roll out new markets on a monthly basis, and we achieved a huge initial victory in our major strategic initiative--electronic bonding with Bell Atlantic," said Royce J. Holland, chairman and chief executive officer of Allegiance Telecom. "The continued progress in automating and scaling up our internal Operations Support Systems and electronic bonding has facilitated continued dramatic growth--50% increase over third quarter--for new access line installations. The fact that our sales and installs for 1998 significantly exceeded our plan is dramatic evidence of the tremendous interest and demand from small and medium-sized business for our 'one-stop shopping' package of services. Our success in the back office arena and the rollout of our data and Internet services provide a solid foundation for continued dramatic growth in 1999."

Network Rollout

Network rollout is proceeding on track, with nine markets operational at the end of 1998 including Atlanta, Boston, Chicago, Dallas, Fort Worth, Los Angeles, New York, Oakland, and San Francisco. Allegiance recently initiated service in the Philadelphia metropolitan area. The Company also plans to initiate service in Washington, D.C. and Northern New Jersey in the first quarter of 1999.

Allegiance continued to see strong gains in its addressable market during the fourth quarter. As of the end of December, the Company is collocated in 101 central offices for unbundled loops, with access to an additional 4 central offices for T1 hub service. This represents an addressable "on-switch" market of approximately 3.6 million local business access lines, an increase of 77% from 3Q98. In addition, Allegiance has 159 additional collocations that are "works-in-process."

At the end of 1998, Allegiance had 7 switches in operation, supporting the following markets: Atlanta, Boston, Chicago, Dallas/Fort Worth, Los Angeles, New York and Oakland/San Francisco. Allegiance completed the installation of its Philadelphia switch in January and is in the process of installing switches in Houston, San Diego and Washington, D.C.

Financial and Operational Highlights

Allegiance again had significant success in its sales efforts, with lines sold increasing from 22,300 in 3Q98 to 43,100 lines in 4Q98, an increase of 93% over 3Q98. Lines installed also showed rapid growth, with lines installed increasing from 14,900 in 3Q98 to 21,800 in 4Q98, an increase of 46% over 3Q98. Bookings through December 1998 resulted in an annualized recurring revenue run rate in excess of $50 million.

The Company's recruitment of its sales force remains on track. Sales force, including managers, grew to 295 people, out of a total Allegiance employee base of 649, as of December 31, 1998. Allegiance continues to believe that one of the keys to achieving its goals is the capturing and retaining of customers through a direct sales force.

Allegiance continues to use its capital to support the development of new markets, resulting in a fourth quarter EBITDA (earnings before interest, taxes, depreciation and amortization, excluding management ownership allocation charge and non-cash deferred compensation expenses) loss of $19.5 million and capital expenditures of $49.9 million.

Continued Increase of "On-Switch" Services

As switches are brought on stream and collocations achieved, the proportion of circuits initially provisioned on Allegiance facilities continues to increase -83% of the new installs were "on- switch," compared to 73% in 3Q98. In the fourth quarter, of the 43,100 lines sold, 91% were "on-switch," compared to 86% in 3Q98. Likewise, of the total lines installed in 1998, 64% were "on-switch" at the end of the fourth quarter, compared to a cumulative total of 47% at the end of 3Q98. In addition, 78% of the total lines sold in 1998 were "on-switch," compared to a cumulative total of 64% at the end of 3Q98.

Data and Internet Services Rollout

Allegiance made great strides in the fourth quarter with the announcement of its first phase of Internet and high-speed data communications service offerings. The first phase of products, now available to Allegiance customers, includes domain name service, business e-mail service, web site hosting and dedicated high-speed Internet access. "To date, very few telecom companies are offering a bundled package of local and long distance services," said Dan Yost, president and chief operating officer of Allegiance Telecom. "With the addition of our new data and Internet services, we are one of the first to provide an expanded envelope of one-stop shopping services, including local, long distance and data services with one point of sale, one consolidated bill and one call for customer service." Allegiance remains on target to introduce its second phase of products in the first quarter of 1999, which will include DSL and Frame Relay, among other products.

In addition to dedicated high-speed Internet access services, Allegiance recently began offering dial-up Internet access in certain of its markets to serve the needs of its smallest business customers.

Implementation of Electronic Bonding with Bell Atlantic

Allegiance achieved another industry "first" when it completed its implementation of electronic bonding with Bell Atlantic. The Allegiance/Bell Atlantic announcement on January 7, 1999 culminated a six-month joint effort between Allegiance and Bell Atlantic to design, implement and test an electronic gateway linking their operations support systems (OSS). This gateway permits Allegiance to create service requests online and monitor in real-time the entire provisioning and installation process. Allegiance expects the electronic bonding of its back office system with Bell Atlantic in New York to significantly reduce the amount of time from initial order entry to installation. Allegiance expects to use the system that it has developed and tested in New York as a basis to implement electronic bonding in other Bell Atlantic states as well as with other incumbent local exchange carriers.

"For a business like ours, which is emphasizing customer service above all, the speed, efficiency and effectiveness with which we can sign up customers and initiate service are of paramount importance," said Holland. "Instead of taking approximately 25 business days for a customer to switch local carriers (without electronic bonding), we believe electronic bonding is the key to shortening that timeframe to approximately five business days."

The lack of electronic bonding between facilities-based carriers has been widely recognized as the principal bottleneck in realizing the competitive local service marketplace envisioned by the Telecommunications Act of 1996. Allegiance believes that its unprecedented arrangement will become a nationwide model for enhancing the ability of competitive carriers to process customer orders more swiftly and accurately. In fact, Allegiance is using the New York model as a nationwide template and has recently begun "fault" testing of electronic bonding with Southwestern Bell in Texas.

Regulatory Certifications

Allegiance is certified to provide competitive local exchange services in nine states, including California, Georgia, Illinois, New Jersey, New York, Maryland, Massachusetts, Pennsylvania, Texas and Virginia. Allegiance currently has applications for CLEC authority pending in the District of Columbia, Colorado, Michigan and Washington State.

Financing Update

"During the fourth quarter, Allegiance used approximately $50 million of its cash and short-term investments to further fund its capital expenditures related to switching platforms, collocations and its data network to support the Company's product suite of local, long distance, data and Internet services," said Thomas M. Lord, executive vice president of corporate development and chief financial officer.

"At December 31, 1998, Allegiance had $405.9 million of cash and short-term investments. This figure does not include restricted cash associated with our senior note financing in July 1998. Allegiance is actively evaluating numerous options to add additional capital to continue funding its aggressive build-out strategy. The Company remains fully funded to free cash flow positive for 18 of its 24 markets."

This quarter included non-cash charges of $6.8 million related to the management ownership allocation associated with the Company's initial public offering. The Company will be expensing the balance of $26.2 million in non-cash charges on a quarterly basis through March 2001.

Corporate Background

Allegiance Telecom, Inc. was founded in April 1997 by a management team led by Royce J. Holland, the former president and COO of MFS Communications Company, Inc., and Thomas M. Lord, former managing director of Bear, Stearns & Co. Inc., where he specialized in the telecommunications, information services and technology industries.

Allegiance offers businesses a complete package of telecommunications services, including local, long distance, international calling, high-speed data transmission and Internet services. Allegiance is targeting 24 major metropolitan areas in the U.S. with its "one-stop shopping" approach. The Company's web address is: www.allegiancetele.com.

Certain statements in this press release constitute "forward-looking statements" within the meaning of the Private Securities Litigation Reform Act of 1995, and the Company intends that such forward-looking statements be subject to the safe harbors created thereby. The words "believes," "expects," "estimates," "anticipates" and "will be" and similar words or expressions identify forward-looking statements made by or on behalf of the Company. These forward-looking statements are subject to many uncertainties and factors which may cause the actual results of the Company to be materially different from any future results expressed or implied by such forward-looking statements. Examples of such uncertainties and factors include, but are not limited to, the extent to which the Company can achieve "electronic bonding" with ILECs, the Company's ability to timely and effectively provision new customers and the Company's continued access to necessary capital. The Company does not undertake any obligation to update or revise any forward-looking statement made by it or on its behalf, whether as a result of new information, future events or otherwise.