QuickLinks -- Click here to rapidly navigate through this document

EXHIBIT 5.1

[ALLEGIANCE TELECOM, INC. LETTERHEAD]

April 15, 2002

Allegiance Telecom, Inc.
9201 Central Expressway
Dallas, TX 75231

        Re: Registration Statement on Form S-8

Ladies and Gentlemen:

        I am the Senior Vice President, General Counsel and Secretary of Allegiance Telecom, Inc., a Delaware corporation. I am issuing this opinion in connection with Allegiance Telecom's proposed registration of an additional 2,000,000 shares (collectively, the "Shares") of its common stock, par value $.01 per share, pursuant to a Registration Statement on Form S-8, filed with the Securities and Exchange Commission on the date hereof under the Securities Act of 1933, as amended (the "Act") (such Registration Statement, as amended or supplemented, is hereinafter referred to as the "Registration Statement"). The Shares are to be issued to certain employees, directors, advisors and consultants of Allegiance Telecom, Inc. and its subsidiaries pursuant to the Fourth Amendment to the Allegiance Telecom, Inc. 1998 Stock Incentive Plan (as amended, the "Plan").

        In that connection, I have examined such corporate proceedings, documents, records and matters of law as I have deemed necessary to enable me to render this opinion.

        For purposes of this opinion, I have assumed the authenticity of all documents submitted to me as originals, the conformity to the originals of all documents submitted to me as copies and the authenticity of the originals of all documents submitted to me as copies. I have also assumed the legal capacity of all natural persons, the genuineness of the signatures of persons signing all documents in connection with which this opinion is rendered, the authority of such persons signing on behalf of the parties thereto other than Allegiance Telecom, Inc. and the due authorization, execution and delivery of all documents by the parties thereto other than Allegiance Telecom, Inc. As to any facts material to the opinions expressed herein, I have relied upon the statements and representations of officers and other representations of Allegiance Telecom, Inc. and others.

        My opinion expressed below is subject to the qualifications that I express no opinion as to the applicability of, compliance with, or effect of (i) any bankruptcy, insolvency, reorganization, fraudulent transfer, fraudulent conveyance, moratorium or other similar law affecting the enforcement of creditors' rights generally; (ii) general principles of equity (regardless of whether enforcement is considered in a proceeding in equity or at law); (iii) public policy considerations which may limit the rights of parties to obtain certain remedies; and (iv) any laws except the General Corporation Law of the State of Delaware.

        Based upon and subject to the foregoing qualifications, assumptions and limitations and the further limitations set forth below, I hereby advise you that in my opinion:

(1)

The Fourth Amendment to the Allegiance Telecom, Inc. 1998 Stock Incentive Plan has been duly adopted by the Board of Directors of Allegiance Telecom, Inc.



(2)

The Shares are duly authorized and validly reserved for issuance pursuant to the Plan and, when: (i) the Registration Statement becomes effective under the Act; (ii) the Shares are issued in accordance with the terms of the Plan and the applicable award agreement; (iii) the recipient provides the full consideration for such Shares as required by the terms of the Plan and the applicable award agreement (assuming in each case the consideration received by Allegiance Telecom, Inc. is at least equal to $0.01 per share); and (iv) certificates representing the Shares have been duly executed and delivered on behalf of Allegiance Telecom, Inc. and

duly countersigned by its transfer agent/registrar, the Shares will be validly issued, fully paid and nonassessable.

        I hereby consent to the filing of this opinion with the Commission as Exhibit 5.1 to the Registration Statement. In giving this consent, I do not thereby admit that I am in the category of persons whose consent is required under Section 7 of the Act or the rules and regulations of the Commission.

        I do not find it necessary for the purposes of this opinion, and accordingly I do not purport to cover herein, the application of the securities or "Blue Sky" laws of the various states to the issuance and sale of the Shares.

        This opinion is limited to the specific issues addressed herein, and no opinion may be inferred or implied beyond that expressly stated herein. I assume no obligation to revise or supplement this opinion should the present laws of the State of Delaware be changed by legislative action, judicial decision or otherwise.

        This opinion is furnished to you in connection with the filing of the Registration Statement and is not to be used, circulated, quoted or otherwise relied upon for any other purpose.

Very truly yours,

/s/ MARK B. TRESNOWSKI Mark B. Tresnowski, Senior Vice President, General Counsel and Secretary

QuickLinks

EXHIBIT 5.1