Exhibit 5.1

                            Willkie Farr & Gallagher
                               787 Seventh Avenue
                               New York, NY 10019




May 1, 2000


NEXTLINK Communications, Inc.
1505 Farm Credit Drive
McLean, Virginia 22102

Re:      NEXTLINK Communications, Inc.
         10 1/2% Senior Notes due 2009 and
         12 1/8% Senior Discount Notes due 2009
         --------------------------------------


Ladies and Gentlemen:

We have acted as counsel for NEXTLINK Communications, Inc., a Delaware
corporation (the "Company"), in connection with the filing by the Company with
the Securities and Exchange Commission (the "Commission") of a registration
statement (as amended by Amendment No.1 on May 1, 2000, the "Registration
Statement") on Form S-4 under the Securities Act of 1933, as amended, relating
to the proposed issuance by the Company of its 10 1/2% Senior Notes due 2009
(the "Senior Notes") and its 12 1/8% Senior Discount Notes due 2009 (the "Senior
Discount Notes" and together with the Senior Notes, the "Securities").

The Senior Notes and the Senior Discount Notes will be issued pursuant to two
indentures between the Company and the United States Trust Company, as trustee
(respectively, the "Senior Notes Indenture" and the "Senior Discount Notes
Indenture"), each of which has been filed as an exhibit to the Registration
Statement. Capitalized terms used herein and not otherwise defined herein have
the meanings ascribed thereto in the Senior Notes Indenture and the Senior
Discount Notes Indenture.

In connection with this opinion, we have examined and relied upon such records,
documents, certificates and other instruments as in our judgment are necessary
or appropriate to form the basis for the opinions set forth herein. In our
examinations, we have assumed the genuineness of all signatures, the legal
capacity of natural persons signing or delivering any instrument, the
authenticity of all documents submitted to us as originals, the conformity to
original documents of all documents submitted to us as



certified or photostatic copies and the authenticity of the originals of such
latter documents.

Based on the foregoing, we are of the opinion that the Senior Notes and the
Senior Discount Notes, when duly issued, authenticated and delivered in
accordance with the provisions of the Senior Notes Indenture and the Senior
Discount Notes Indenture, respectively, will constitute valid and binding
obligations of the Company.

We do not express any opinion with respect to matters governed by any laws other
than the laws of the State of New York and the federal laws of the United States
of America.

We know that we may be referred to as counsel who has passed upon the validity
of the issuance of the Securities on behalf of the Company in the Registration
Statement filed with the Commission, and we hereby consent to such use of our
name in said Registration Statement and to the filing of this opinion with said
Registration Statement as Exhibit 5.1 thereto.

Very truly yours,

/s/ Willkie Farr & Gallagher