<PAGE>   1


                          REGISTRATION RIGHTS AGREEMENT

                          Dated as of January 20, 2000

                                     between

                          NEXTLINK Communications, Inc.


                                       and

               The Purchasers Listed on the Signature Pages Hereto





<PAGE>   2

       REGISTRATION RIGHTS AGREEMENT, dated as of January 20, 2000 between
NEXTLINK Communications, Inc., a Delaware corporation (the "Company") and the
entities listed on the signature pages hereto under the caption "Purchasers"
(each a "Purchaser" and, collectively, the "Purchasers").

       The Company and the Purchasers have entered it into a Securities Purchase
Agreement (the "Purchase Agreement") dated as of December 7, 1999 pursuant to
which simultaneously herewith, the Purchasers are purchasing (i) an aggregate of
584,375 shares of the Company's Series C Preferred Stock, par value $0.01 per
share (the "Series C Preferred Stock") and (ii) an aggregate of 265,625 shares
of the Company's Series D Preferred Stock, par value $0.01 per share (the
"Series D Preferred Stock" and, collectively with the Series C Preferred Stock,
the "Preferred Shares").

       As part of, and as consideration for, the acquisition of the Preferred
Shares by the Purchasers from the Company on the date hereof and from time to
time hereafter, the Company hereby grants to the Purchasers certain registration
and other rights with respect to its shares of Class A Common Stock as more
fully set forth herein.

       Accordingly, the parties hereto agree as follows:

       1.     Definitions. As used herein, unless the context otherwise
requires, the following terms have the following respective meanings:

       "Certificate of Incorporation" means the Certificate of Incorporation of
the Company, as it may be amended or restated hereafter from time to time.

       "Commission" means the Securities and Exchange Commission or any other
Federal agency at the time administering the Securities Act.

       "Common Stock" means any shares of Class A Common Stock, par value $0.01
per share, of the Company, now or hereafter authorized to be issued, and any and
all securities of any kind whatsoever of the Company which may be exchanged for
or converted into Common Stock, any and all securities of any kind whatsoever of
the Company which may be issued on or after the date hereof in respect of, in
exchange for, or upon conversion of shares of Common Stock pursuant to a merger,
consolidation, stock split, stock dividend, recapitalization of the Company or
otherwise.

       "Exchange Act" means the Securities Exchange Act of 1934, as amended, or
any similar Federal statute, and the rules and regulations of the Commission
thereunder, all as the same shall be in effect at the time. Reference to a
particular section of the Exchange Act shall include a reference to the
comparable section, if any, of any such similar Federal statute.


<PAGE>   3

       "Person" means a corporation, an association, a partnership, an
organization, a business, a trust, an individual, or any other entity or
organization, including a government or political subdivision or an
instrumentality or agency thereof.

       "Registrable Securities" means (i) any shares of Common Stock issued or
issuable upon the conversion of any Preferred Shares held by the Purchasers and
(ii) any shares of Common Stock issued with respect to the Common Stock referred
to in clause (i) by way of a stock dividend, stock split or reverse stock split
or in connection with a combination of shares, recapitalization, merger,
consolidation or otherwise. As to any particular Registrable Securities, such
securities shall cease to be Registrable Securities (a) when a registration
statement with respect to the sale of such securities shall have become
effective under the Securities Act and such securities shall have been disposed
of in accordance with such registration statement, (b) when such securities
shall have been otherwise transferred, new certificates for them not bearing a
legend restricting further transfer shall have been delivered by the Company and
subsequent public distribution of them shall not require registration of them
under the Securities Act, (c) when such securities are eligible for sale under
Rule 144(k) or any successor provision, or (d) when such securities shall have
been sold as permitted by, and in compliance with, the Securities Act.

       "Registration Expenses" means all expenses incident to the registration
and disposition of the Registrable Securities pursuant to Section 2 hereof,
including, without limitation, all registration, filing and applicable national
securities exchange fees, all fees and expenses of complying with state
securities or blue sky laws (including fees and disbursements of counsel to the
underwriters or the Purchasers in connection with "blue sky" qualification of
the Registrable Securities and determination of their eligibility for investment
under the laws of the various jurisdictions), all word processing, duplicating
and printing expenses, all messenger and delivery expenses, the fees and
disbursements of counsel for the Company and of its independent public
accountants, including the expenses of "cold comfort" letters or any special
audits required by, or incident to, such registration, all fees and
disbursements of underwriters (other than underwriting discounts and
commissions), all transfer taxes, and all fees and expenses of counsel to the
Purchasers; provided, however, that Registration Expenses shall exclude, and the
Purchasers shall pay, underwriting discounts and commissions in respect of the
Registrable Securities being registered.

       "Securities Act" means the Securities Act of 1933, as amended, or any
similar Federal statute, and the rules and regulations of the Commission
thereunder, all as the same shall be in effect at the time. References to a
particular section of the Securities Act shall include a reference to the
comparable section, if any, of any such similar Federal statute.



                                     - 2 -
<PAGE>   4

       2.     Registration Under Securities Act, etc.

              2.1    Registration on Request.

                     (a)    Request. At any time or from time to time after the
Purchasers are permitted to transfer Registrable Securities pursuant to Section
4.15 of the Purchase Agreement, the Purchasers shall have the right to require
the Company to effect the registration under the Securities Act of all or part
of the Registrable Securities, by delivering a written request therefor to the
Company specifying the number of shares of Registrable Securities and the
intended method of distribution. The Company shall (i) use its reasonable best
efforts to effect the registration under the Securities Act (including by means
of a shelf registration pursuant to Rule 415 under the Securities Act if so
requested in such request and if the Company is then eligible to use such a
registration) of the Registrable Securities which the Company has been so
requested to register by the Purchasers, for distribution in accordance with the
intended method of distribution set forth in the written request delivered by
the Purchasers, such registration to be effected as expeditiously as possible
(but in any event within 90 days of receipt of a written request), and (ii) if
requested by the Purchasers, use its reasonable best efforts to obtain
acceleration of the effective date of the registration statement relating to
such registration.

                     (b)    Registration of Other Securities. Whenever the
Company shall effect a registration pursuant to this Section 2.1 in connection
with an underwritten offering by the Purchasers of Registrable Securities, no
securities other than Registrable Securities shall be included among the
securities covered by such registration if inclusion of such other securities
would result in a request by the managing underwriters for a reduction in the
number of Registrable Securities requested to be so registered, except as
required by the terms of registration rights agreements in effect on the date
hereof.

                     (c)    Registration Statement Form. Registrations under
this Section 2.1 shall be on such appropriate registration form of the
Commission as, subject to clause (a)(i) above, shall be selected by the Company
and as shall be reasonably acceptable to the Purchasers. The Company agrees to
include in any such registration statement all information which, in the opinion
of counsel to the Purchasers and counsel to the Company, is necessary or
desirable to be included therein.

                     (d)    Expenses. The Company shall pay all Registration
Expenses in connection with any registration requested pursuant to this Section
2.1.

                     (e)    Effective Registration Statement. A registration
requested pursuant to this Section 2.1 shall not be deemed to have been effected
(including for purposes of paragraph (h) of this Section 2.1) (i) unless a
registration


                                     - 3 -
<PAGE>   5

statement with respect thereto has become effective and has been kept
continuously effective for a period of at least 365 days (or such shorter period
which shall terminate when all the Registrable Securities covered by such
registration statement have been sold pursuant thereto), (ii) if after it has
become effective, such registration is interfered with by any stop order,
injunction or other order or requirement of the Commission or other governmental
agency or court for any reason not attributable to the Purchasers and has not
thereafter become effective, or (iii) if the conditions to closing specified in
the underwriting agreement, if any, entered into in connection with such
registration are not satisfied or waived.

                     (f)    Selection of Underwriters. The underwriters of each
underwritten offering of the Registrable Securities so to be registered shall be
selected by the Purchasers, subject to the Company's approval, which approval
shall not be unreasonably withheld.

                     (g)    Right to Withdraw. If the managing underwriter of
any underwritten offering shall advise the Purchasers that the Registrable
Securities covered by the registration statement cannot be sold in such offering
within a price range acceptable to the Purchasers, then the Purchasers shall
have the right to notify the Company in writing that they have determined that
the registration statement be abandoned or withdrawn, in which event the Company
shall abandon or withdraw such registration statement. In the event of such
abandonment or withdrawal, such request shall not be counted for purposes of the
requests for registration to which the Purchasers are entitled pursuant to this
Section 2.1, and the Purchasers shall pay, or reimburse the Company for, all
Registration Expenses related thereto.

                     (h)    Limitations on Registration on Request. The
Purchasers shall be entitled to require the Company to effect, and the Company
shall be required to effect, three registrations in the aggregate pursuant to
this Section 2.1.

                     (i)    Postponement. The Company shall be entitled once in
any six-month period to postpone for a reasonable period of time (but not
exceeding 60 days) (the "Postponement Period") the filing of any registration
statement required to be prepared and filed by it pursuant to this Section 2.1
if the Company determines, in its reasonable judgment, that such registration
and offering would materially interfere with any material financing, corporate
reorganization or other material transaction involving the Company or any
subsidiary, or would require premature disclosure thereof, and promptly gives
the Purchasers written notice of such determination, containing a general
statement of the reasons for such postponement (which the Purchasers shall
maintain in strict confidence in accordance with the Confidentiality Agreement
(as defined in the Purchase Agreement)) and an approximation of the anticipated
delay. If the Company shall so postpone the filing of a registration statement,
(i) the Company shall use its


                                     - 4 -
<PAGE>   6

reasonable best efforts to limit the delay to as short a period as is
practicable and (ii) the Purchasers shall have the right to withdraw the request
for registration by giving written notice to the Company at any time and, in the
event of such withdrawal, such request shall not be counted for purposes of the
requests for registration to which the Purchasers are entitled pursuant to this
Section 2.1.

                     (j)    Shelf Registration. If the Purchasers request that
the Company effect a registration of Registrable Securities by means of shelf
registration pursuant to Rule 415 under the Securities Act (a "Shelf
Registration Statement"), in addition to the other requirements contained
herein, the Company shall, at its cost, use its reasonable best efforts to keep
the Shelf Registration Statement continuously effective in order to permit the
Prospectus forming part thereof to be usable by the Purchasers until such time
as all the Registrable Securities covered by the Shelf Registration Statement
have been sold pursuant to the Shelf Registration Statement or cease to be
outstanding (the "Effectiveness Period"); provided, however, that the
Effectiveness Period in respect of the Shelf Registration Statement shall be
extended to the extent required to permit dealers to comply with the applicable
prospectus delivery requirements under the Securities Act and as otherwise
provided herein.

              2.2    Incidental Registration.

                     (a)    Right to Include Registrable Securities. If the
Company at any time proposes to register any of its securities for the account
of any other stockholder under the Securities Act by registration on Form S-1,
S-2 or S-3 or any successor or similar form(s) (except registrations on any such
Form or similar form(s) solely for registration of securities in connection with
an employee benefit plan or dividend reinvestment plan or a merger or
consolidation or incidental to an issuance of securities under Rule 144A under
the Securities Act), it will each such time give prompt written notice to the
Purchasers of its intention to do so and of the Purchasers' rights under this
Section 2.2. At any time or from time to time after the Purchasers are permitted
to transfer Registrable Securities pursuant to Section 4.15 of the Purchase
Agreement, upon the written request of the Purchasers (which request shall
specify the maximum number of Registrable Securities intended to be disposed of
by the Purchasers), made as promptly as practicable and in any event within 30
days after the receipt of any such notice (10 days if the Company states in such
written notice or gives telephonic notice to the Purchasers, with written
confirmation to follow promptly thereafter, stating that (i) such registration
will be on Form S-3 and (ii) such shorter period of time is required because of
a planned filing date), the Company shall use its reasonable best efforts to
effect the registration under the Securities Act of all Registrable Securities
which the Company has been so requested to register by the Purchasers; provided,
however, that if, at any time after giving written notice of its intention to
register any securities and prior to the effective date of the registration
statement filed in connection


                                     - 5 -
<PAGE>   7

with such registration, the Company shall determine for any reason not to
register or to delay registration of such securities, the Company shall give
written notice of such determination and its reasons therefor (which the
Purchasers will hold in strict confidence in accordance with the Confidentiality
Agreement) to the Purchasers and (i) in the case of a determination not to
register, shall be relieved of its obligation to register any Registrable
Securities in connection with such registration (but not from any obligation of
the Company to pay the Registration Expenses in connection therewith), without
prejudice, however, to the rights of the Purchasers to request that such
registration be effected as a registration under Section 2.1 and (ii) in the
case of a determination to delay registering, shall be permitted to delay
registering any Registrable Securities, for the same period as the delay in
registering such other securities. No registration effected under this Section
2.2 shall relieve the Company of its obligation to effect any registration upon
request under Section 2.1. The Company will pay all Registration Expenses in
connection with any registration of Registrable Securities requested pursuant to
this Section 2.2.

                     (b)    Right to Withdraw. The Purchasers shall have the
right to withdraw its request for inclusion of its Registrable Securities in any
registration statement pursuant to this Section 2.2 at any time prior to the
execution of an underwriting agreement with respect thereto by giving written
notice to the Company of its request to withdraw.

                     (c)    Priority in Incidental Registrations. If the
managing underwriter of any underwritten offering shall inform the Company by
letter of its belief that the number of Registrable Securities requested to be
included in such registration, when added to the number of other securities to
be offered in such registration, would materially adversely affect such
offering, then the Company shall include in such registration, to the extent of
the number and type which the Company is so advised can be sold in (or during
the time of) such offering without so materially adversely affecting such
offering (the "Section 2.2 Sale Amount") and to the fullest extent permitted by
the terms of applicable registration rights agreements in effect on the date
hereof, the securities proposed by the other stockholders triggering such
incidental registration, the Registrable Securities requested by the Purchasers
to be included in such registration pursuant to Section 2.2(a) and any other
securities of the Company requested to be included in such registration by any
other holder having the right to include securities on a pro rata basis (in an
amount in the aggregate equal to the Section 2.2 Sale Amount), based on the pro
rata amount of shares of Common Stock held, or obtainable by exercise or
conversion of other securities of the Company, by the Purchasers or such holder.

                     (d)    Plan of Distribution. Any participation by holders
of Registrable Securities in a registration by the Company shall be in
accordance with the


                                     - 6 -
<PAGE>   8

Company's plan of distribution, provided that the Purchasers shall in
consultation with the Company have the right to select a co-managing
underwriter.

                     2.3    Registration Procedures. If and whenever the Company
is required to use its reasonable best efforts to effect the registration of any
Registrable Securities under the Securities Act as provided in Sections 2.1 and
2.2 hereof, the Company shall as expeditiously as possible:

                     (a)    prepare and file with the Commission as soon as
              practicable the requisite registration statement to effect such
              registration (and shall include all financial statements required
              by the Commission to be filed therewith) and thereafter use its
              reasonable best efforts to cause such registration statement to
              become effective; provided, however, that before filing such
              registration statement (including all exhibits) or any amendment
              or supplement thereto or comparable statements under securities or
              blue sky laws of any jurisdiction, the Company shall as promptly
              as practicable furnish such documents to the Purchasers and each
              underwriter, if any, participating in the offering of the
              Registrable Securities and their respective counsel, which
              documents will be subject to the review and comments of the
              Purchasers, each underwriter and their respective counsel; and
              provided, further, however, that the Company may discontinue any
              registration of its securities which are not Registrable
              Securities at any time prior to the effective date of the
              registration statement relating thereto;

                     (b)    notify the Purchasers of the Commission's requests
              for amending or supplementing the registration statement and the
              prospectus, and prepare and file with the Commission such
              amendments and supplements to such registration statement and the
              prospectus used in connection therewith as may be necessary to
              keep such registration statement effective and to comply with the
              provisions of the Securities Act with respect to the disposition
              of all Registrable Securities covered by such registration
              statement for such period as shall be required for the disposition
              of all of such Registrable Securities in accordance with the
              intended method of distribution thereof; provided, that except
              with respect to any such registration statement filed pursuant to
              Rule 415 under the Securities Act, such period need not exceed 365
              days;

                     (c)    furnish, without charge, to the Purchasers and each
              underwriter such number of conformed copies of such registration
              statement and of each such amendment and supplement thereto (in
              each case including all exhibits), such number of copies of the
              prospectus contained in such registration statement (including
              each preliminary prospectus and any



                                     - 7 -
<PAGE>   9

              summary prospectus) and any other prospectus filed under Rule 424
              under the Securities Act, in conformity with the requirements of
              the Securities Act, and such other documents, as the Purchasers
              and such underwriters may reasonably request;

                     (d)    use its reasonable best efforts (i) to register or
              qualify all Registrable Securities and other securities covered by
              such registration statement under such securities or blue sky laws
              of such States of the United States of America where an exemption
              is not available and as the Purchasers or any managing underwriter
              shall reasonably request, (ii) to keep such registration or
              qualification in effect for so long as such registration statement
              remains in effect, and (iii) to take any other action which may be
              reasonably necessary or advisable to enable the Purchasers to
              consummate the disposition in such jurisdictions of the securities
              to be sold by the Purchasers, except that the Company shall not
              for any such purpose be required to qualify generally to do
              business as a foreign corporation in any jurisdiction wherein it
              would not but for the requirements of this subsection (d) be
              obligated to be so qualified or to consent to general service of
              process in any such jurisdiction;

                     (e)    use its reasonable best efforts to cause all
              Registrable Securities covered by such registration statement to
              be registered with or approved by such other federal or state
              governmental agencies or authorities as may be necessary in the
              opinion of counsel to the Company and counsel to the Purchasers to
              consummate the disposition of such Registrable Securities;

                     (f)    furnish to the Purchasers and each underwriter, if
              any, participating in the offering of the securities covered by
              such registration statement, a signed counterpart of (i) an
              opinion of counsel for the Company, and (ii) a "comfort" letter
              signed by the independent public accountants who have certified
              the Company's or any other entity's financial statements included
              or incorporated by reference in such registration statement,
              covering substantially the same matters with respect to such
              registration statement (and the prospectus included therein) and,
              in the case of the accountants' comfort letter, with respect to
              events subsequent to the date of such financial statements, as are
              customarily covered in opinions of issuer's counsel and in
              accountants' comfort letters delivered to the underwriters in
              underwritten public offerings of securities (and dated the dates
              such opinions and comfort letters are customarily dated) and, in
              the case of the legal opinion, such other legal matters;



                                     - 8 -
<PAGE>   10

                     (g)    promptly notify the Purchasers and each managing
              underwriter, if any, participating in the offering of the
              securities covered by such registration statement (i) when such
              registration statement, any pre-effective amendment, the
              prospectus or any prospectus supplement related thereto or
              post-effective amendment to such registration statement has been
              filed, and, with respect to such registration statement or any
              post-effective amendment, when the same has become effective; (ii)
              of any request by the Commission for amendments or supplements to
              such registration statement or the prospectus related thereto or
              for additional information; (iii) of the issuance by the
              Commission of any stop order suspending the effectiveness of such
              registration statement or the initiation of any proceedings for
              that purpose; (iv) of the receipt by the Company of any
              notification with respect to the suspension of the qualification
              of any of the Registrable Securities for sale under the securities
              or blue sky laws of any jurisdiction or the initiation of any
              proceeding for such purpose; (v) at any time when a prospectus
              relating thereto is required to be delivered under the Securities
              Act, upon discovery that, or upon the happening of any event as a
              result of which, the prospectus included in such registration
              statement, as then in effect, includes an untrue statement of a
              material fact or omits to state any material fact required to be
              stated therein or necessary to make the statements therein not
              misleading, in the light of the circumstances under which they
              were made, and in the case of this clause (v), at the request of
              the Purchasers promptly prepare and furnish to the Purchasers and
              each managing underwriter, if any, participating in the offering
              of the Registrable Securities, a reasonable number of copies of a
              supplement to or an amendment of such prospectus as may be
              necessary so that, as thereafter delivered to the purchasers of
              such securities, such prospectus shall not include an untrue
              statement of a material fact or omit to state a material fact
              required to be stated therein or necessary to make the statements
              therein not misleading in the light of the circumstances under
              which they were made; and (vi) at any time when the
              representations and warranties of the Company contemplated by
              Section 2.4(a) or (b) hereof cease to be true and correct;

                     (h)    otherwise comply with all applicable rules and
              regulations of the Commission, and make available to its security
              holders, as soon as reasonably practicable, an earnings statement
              covering the period of at least twelve months beginning with the
              first full calendar month after the effective date of such
              registration statement, which earnings statement shall satisfy the
              provisions of Section 11(a) of the Securities Act and Rule 158
              promulgated thereunder, and promptly furnish to the Purchasers a
              copy of any amendment or supplement to such registration statement
              or prospectus;

                                     - 9 -
<PAGE>   11

                     (i)    provide and cause to be maintained a transfer agent
              and registrar (which, in each case, may be the Company) for all
              Registrable Securities covered by such registration statement from
              and after a date not later than the effective date of such
              registration;

                     (j)    (i) use its reasonable best efforts to cause all
              Registrable Securities covered by such registration statement to
              be listed on the NASDAQ "national market system" or the principal
              securities exchange on which similar securities issued by the
              Company are then listed (if any), if the listing of such
              Registrable Securities is then permitted under the rules of such
              exchange, or (ii) if no similar securities are then so listed, use
              its reasonable best efforts to (x) cause all such Registrable
              Securities to be listed on a national securities exchange or (y)
              failing that, secure designation of all such Registrable
              Securities as a NASDAQ "national market system security" within
              the meaning of Rule 11Aa2-1 of the Commission or (z) failing that,
              to secure NASDAQ authorization for such shares and, without
              limiting the generality of the foregoing, to arrange for at least
              two market makers to register as such with respect to such shares
              with the National Association of Securities Dealers, Inc.;

                     (k)    deliver promptly to counsel to the Purchasers and
              each underwriter, if any, participating in the offering of the
              Registrable Securities, copies of all correspondence between the
              Commission and the Company, its counsel or auditors and all
              memoranda relating to discussions with the Commission or its staff
              with respect to such registration statement;

                     (l)    use its reasonable best efforts to obtain the
              withdrawal of any order suspending the effectiveness of the
              registration statement;

                     (m)    provide a CUSIP number for all Registrable
              Securities, no later than the effective date of the registration
              statement; and

                     (n)    in connection with any underwritten public offering,
              make available its senior executive officers, directors and
              chairman and otherwise provide reasonable assistance to the
              underwriters (taking into account the needs of the Company's
              business) in their marketing of Registrable Securities.

The Company may require the Purchasers to furnish the Company such information
regarding the Purchasers and the distribution of the Registrable Securities as
the Company may from time to time reasonably request in writing.



                                     - 10 -
<PAGE>   12

              The Purchasers agrees that upon receipt of any notice from the
Company of the happening of any event of the kind described in paragraph
(g)(iii) or (v) of this Section 2.3, the Purchasers will, to the extent
appropriate, discontinue their disposition of Registrable Securities pursuant to
the registration statement relating to such Registrable Securities until, in the
case of paragraph (g)(v) of this Section 2.3, their receipt of the copies of the
supplemented or amended prospectus contemplated by paragraph (g)(v) of this
Section 2.3 and, if so directed by the Company, will deliver to the Company (at
the Company's expense) all copies, other than permanent file copies, then in
their possession, of the prospectus relating to such Registrable Securities
current at the time of receipt of such notice. If the disposition by the
Purchasers of their securities is discontinued pursuant to the foregoing
sentence, the Company shall extend the period of effectiveness of the
registration statement by the number of days during the period from and
including the date of the giving of notice to and including the date when the
Purchasers shall have received copies of the supplemented or amended prospectus
contemplated by paragraph (g)(v) of this Section 2.3; and, if the Company shall
not so extend such period, the Purchasers' request pursuant to which such
registration statement was filed shall not be counted for purposes of the
requests for registration to which the Purchasers are entitled pursuant to
Section 2.1 hereof.

              2.4    Underwritten Offerings.

                     (a)    Requested Underwritten Offerings. If requested by
the underwriters for any underwritten offering by the Purchasers pursuant to a
registration requested under Section 2.1, the Company shall enter into a
customary underwriting agreement (in the form of underwriting agreement used at
such time by the managing underwriter(s)) with a managing underwriter or
underwriters selected by the Purchasers. Such underwriting agreement shall be
satisfactory in form and substance to the Purchasers and shall contain such
representations and warranties by, and such other agreements on the part of, the
Company and such other terms as are generally prevailing in agreements of the
managing underwriter(s), including, without limitation, their customary
provisions relating to indemnification and contribution. The Purchasers shall be
party to such underwriting agreement and may, at their option, require that any
or all of the representations and warranties by, and the other agreements on the
part of, the Company to and for the benefit of such underwriters shall also be
made to and for the benefit of the Purchasers and that any or all of the
conditions precedent to the obligations of such underwriters under such
underwriting agreement be conditions precedent to the obligations of the
Purchasers.

                     (b)    Incidental Underwritten Offerings. In the case of a
registration pursuant to Section 2.2 hereof, if the Company shall have
determined to enter into any underwriting agreements in connection therewith,
all of the Registrable Securities to be included in such registration shall be
subject to such underwriting


                                     - 11 -
<PAGE>   13

agreements. The Purchasers may, at their option, require that any or all of the
representations and warranties by, and the other agreements on the part of, the
Company to and for the benefit of such underwriters shall also be made to and
for the benefit of the Purchasers and that any or all of the conditions
precedent to the obligations of such underwriters under such underwriting
agreement be conditions precedent to the obligations of the Purchasers.

              2.5    Preparation; Reasonable Investigation. In connection with
the preparation and filing of each registration statement under the Securities
Act pursuant to this Agreement, the Company will give the Purchasers, their
underwriters, if any, and their respective counsel, accountants and other
representatives and agents the opportunity to participate in the preparation of
such registration statement, each prospectus included therein or filed with the
Commission, and each amendment thereof or supplement thereto, and give each of
them such access to its books and records and such opportunities to discuss the
business of the Company with its officers and employees and the independent
public accountants who have certified its financial statements, and supply all
other information reasonably requested by each of them, as shall be necessary or
appropriate, in the opinion of the Purchasers and such underwriters' respective
counsel, to conduct a reasonable investigation within the meaning of the
Securities Act.

              2.6    Indemnification.

                     (a)    Indemnification by the Company. The Company agrees
that in the event of any registration of any securities of the Company under the
Securities Act, the Company shall, and hereby does, indemnify and hold harmless
the Purchasers, their respective directors, officers, members, partners, agents
and affiliates and each other Person who participates as an underwriter in the
offering or sale of such securities and each other Person, if any, who controls
the Purchasers or any such underwriter within the meaning of the Securities Act,
against any losses, claims, damages, or liabilities, joint or several, to which
the Purchasers or any such director, officer, member, partner, agent or
affiliate or underwriter or controlling person may become subject under the
Securities Act or otherwise, insofar as such losses, claims, damages or
liabilities, joint or several (or actions or proceedings, whether commenced or
threatened, in respect thereof), arise out of or are based upon (i) any untrue
statement or alleged untrue statement of any material fact contained in any
registration statement under which such securities were registered under the
Securities Act, any preliminary prospectus, final prospectus or summary
prospectus contained therein, or any amendment or supplement thereto, (ii) any
omission or alleged omission to state therein a material fact required to be
stated therein or necessary to make the statements therein in light of the
circumstances in which they were made not misleading, or (iii) any violation by
the Company of any federal, state or common law rule or regulation applicable to
the Company and relating to action required of or inaction by the Company in
connection with any such registration, and the Company shall


                                     - 12 -
<PAGE>   14

reimburse the Purchasers and each such director, officer, member, partner, agent
or affiliate, underwriter and controlling Person for any legal or any other
expenses reasonably incurred by them in connection with investigating or
defending any such loss, claim, liability, action or proceeding; provided that
the Company shall not be liable in any such case to the Purchasers or any such
director, officer, member, partner, agent, affiliate, or controlling person to
the extent that any such loss, claim, damage, liability (or action or proceeding
in respect thereof) or expense arises out of or is based upon an untrue
statement or alleged untrue statement or omission or alleged omission made in
such registration statement, any such preliminary prospectus, final prospectus,
summary prospectus, amendment or supplement in reliance upon and in conformity
with written information furnished to the Company through an instrument duly
executed by or on behalf of the Purchasers, specifically stating that it is for
use in the preparation thereof. Such indemnity shall remain in full force
regardless of any investigation made by or on behalf of the Purchasers or any
such director, officer, member, partner, agent, affiliate, underwriter or
controlling Person and shall survive the transfer of such securities by the
Purchasers.

                     (b)    Indemnification by the Purchasers. As a condition to
including any Registrable Securities in any registration statement, the Company
shall have received an undertaking reasonably satisfactory to it from the
Purchasers so including any Registrable Securities to indemnify and hold
harmless (in the same manner and to the same extent as set forth in paragraph
(a) of this Section 2.6) the Company, and each director of the Company, each
officer of the Company and each other Person, if any, who controls the Company
within the meaning of the Securities Act, with respect to any statement or
alleged statement in or omission or alleged omission from such registration
statement, any preliminary prospectus, final prospectus or summary prospectus
contained therein, or any amendment or supplement thereto, but only to the
extent such statement or alleged statement or omission or alleged omission was
made in reliance upon and in conformity with written information furnished to
the Company through an instrument duly executed by the Purchasers specifically
stating that it is for use in the preparation of such registration statement,
preliminary prospectus, final prospectus, summary prospectus, amendment or
supplement; provided, however, that the liability of such indemnifying party
under this Section 2.6(b) shall be limited to the amount of proceeds (net of
expenses and underwriting discounts and commissions) received by such
indemnifying party in the offering giving rise to such liability. Such indemnity
shall remain in full force and effect, regardless of any investigation made by
or on behalf of the Company or any such director, officer or controlling Person
and shall survive the transfer of such securities by the Purchasers.

                     (c)    Notices of Claims, etc. Promptly after receipt by an
indemnified party of notice of the commencement of any action or proceeding
involving a claim referred to in the preceding subsections of this Section 2.6,
such indemnified party


                                     - 13 -
<PAGE>   15

shall, if a claim in respect thereof is to be made against an indemnifying
party, give written notice to the latter of the commencement of such action or
proceeding; provided, however, that the failure of any indemnified party to give
notice as provided herein shall not relieve the indemnifying party of its
obligations under the preceding subsections of this Section 2.6, except to the
extent that the indemnifying party is actually prejudiced by such failure to
give notice, and shall not relieve the indemnifying party from any liability
which it may have to the indemnified party otherwise than under this Section
2.6. In case any such action or proceeding is brought against an indemnified
party, the indemnifying party shall be entitled to participate therein and,
unless in the opinion of outside counsel to the indemnified party a conflict of
interest between such indemnified and indemnifying parties may exist in respect
of such claim, to assume the defense thereof, jointly with any other
indemnifying party similarly notified to the extent that it may wish, with
counsel reasonably satisfactory to such indemnified party; provided, however,
that if the defendants in any such action or proceeding include both the
indemnified party and the indemnifying party and if in the opinion of outside
counsel to the indemnified party there may be legal defenses available to such
indemnified party and/or other indemnified parties which are different from or
in addition to those available to the indemnifying party, the indemnified party
or parties shall have the right to select separate counsel to defend such action
or proceeding on behalf of such indemnified party or parties, provided, however,
that the indemnifying party shall be obligated to pay for only one counsel and
one local counsel for all indemnified parties. After notice from the
indemnifying party to such indemnified party of its election so to assume the
defense thereof and approval by the indemnified party of such counsel, the
indemnifying party shall not be liable to such indemnified party for any legal
expenses subsequently incurred by the latter in connection with the defense
thereof other than reasonable costs of investigation (unless the first proviso
in the preceding sentence shall be applicable). No indemnifying party shall be
liable for any settlement of any action or proceeding effected without its
written consent. No indemnifying party shall, without the consent of the
indemnified party, consent to entry of any judgment or enter into any settlement
which does not include as an unconditional term thereof the giving by the
claimant or plaintiff to such indemnified party of a release from all liability
in respect to such claim or litigation.

                     (d)    Contribution. If the indemnification provided for in
this Section 2.6 shall for any reason be held by a court to be unavailable to an
indemnified party under subsection (a) or (b) hereof in respect of any loss,
claim, damage or liability, or any action in respect thereof, then, in lieu of
the amount paid or payable under subsection (a) or (b) hereof, the indemnified
party and the indemnifying party under subsection (a) or (b) hereof shall
contribute to the aggregate losses, claims, damages and liabilities (including
legal or other expenses reasonably incurred in connection with investigating the
same), (i) in such proportion as is appropriate to reflect the relative fault of
the indemnifying party on the one hand, and the indemnified party on the other,
which resulted in such loss, claim, damage or liability, or action in respect
thereof, with respect



                                     - 14 -
<PAGE>   16

to the statements or omissions which resulted in such loss, claim, damage or
liability, or action in respect thereof, as well as any other relevant equitable
considerations, or (ii) if the allocation provided by clause (i) above is not
permitted by applicable law or if the allocation provided in this clause (ii)
provides a greater amount to the indemnified party than clause (i) above, in
such proportion as shall be appropriate to reflect not only the relative fault
but also the relative benefits received by the indemnifying party and the
indemnified party from the offering of the securities covered by such
registration statement as well as any other relevant equitable considerations.
The parties hereto agree that it would not be just and equitable if
contributions pursuant to this Section 2.6(d) were to be determined by pro rata
allocation or by any other method of allocation which does not take into account
the equitable considerations referred to in the preceding sentence of this
Section 2.6(d). No Person guilty of fraudulent misrepresentation (within the
meaning of Section 11(f) of the Securities Act) shall be entitled to
contribution from any Person who was not guilty of such fraudulent
misrepresentation. In addition, no Person shall be obligated to contribute
hereunder any amounts in payment for any settlement of any action or claim
effected without such Person's consent, which consent shall not be unreasonably
withheld. Notwithstanding anything in this subsection (d) to the contrary, no
indemnifying party (other than the Company) shall be required to contribute any
amount in excess of the proceeds (net of expenses and underwriting discounts and
commissions) received by such party from the sale of the Registrable Securities
in the offering to which the losses, claims, damages or liabilities of the
indemnified parties relate.

                     (e)    Other Indemnification. Indemnification and
contribution similar to that specified in the preceding subsections of this
Section 2.6 (with appropriate modifications) shall be given by the Company and
the Purchasers with respect to any required registration or other qualification
of securities under any federal, state or blue sky law or regulation of any
governmental authority other than the Securities Act. The indemnification
agreements contained in this Section 2.6 shall be in addition to any other
rights to indemnification or contribution which any indemnified party may have
pursuant to law or contract and shall remain operative and in full force and
effect regardless of any investigation made by or on behalf of any indemnified
party and shall survive the transfer of any of the Registrable Securities by the
Purchasers.

                     (f)    Indemnification Payments. The indemnification and
contribution required by this Section 2.6 shall be made by periodic payments of
the amount thereof during the course of the investigation or defense, as and
when bills are received or expense, loss, damage or liability is incurred.

              2.7    Unlegended Certificates. In connection with the offering of
any Registrable Securities registered pursuant to this Section 2, the Company
shall (i) facilitate the timely preparation and delivery to the Purchasers and
the underwriters, if



                                     - 15 -
<PAGE>   17

any, participating in such offering, of unlegended certificates representing
ownership of such Registrable Securities being sold in such denominations and
registered in such names as requested by the Purchasers or such underwriters and
(ii) instruct any transfer agent and registrar of such Registrable Securities to
release any stop transfer orders with respect to any such Registrable
Securities.

              2.8    Manner of Sale. So long as the Purchasers own in excess of
2.5% of the fully diluted Common Stock (after giving effect to the exercise of
all outstanding options, warrants and other rights to purchase Common Stock
whether or not such options, warrants or other rights are then exercisable (the
"Threshold Amount")), the Purchasers agree that, except as provided below or
except with the written consent of the Company (which consent shall not be
unreasonably withheld), the Purchasers shall sell or otherwise effectuate a
distribution of Registrable Securities only (i) pursuant to one or more firm
commitment underwritten public offerings or (ii) in one or more block trades.
Notwithstanding anything to the contrary set forth above, at any time while the
Purchasers own an amount of Common Stock in excess of the Threshold Amount, the
Purchasers shall have the right to effectuate a distribution of Registrable
Securities in any other manner, including pursuant to a Shelf Registration
Statement, if in the opinion of a nationally recognized investment banker
selected by the Company and the Purchasers, distributions of Registrable
Securities made in the manner proposed by the Purchasers would not adversely
affect the market for the Common Stock. Nothing contained herein shall be deemed
to restrict the Purchasers from transferring any of the Common Stock at any time
in accordance with the terms of the Purchase Agreement.

              2.9    No Required Sale. Nothing in this Agreement shall be deemed
to create an independent obligation on the part of the Purchasers to sell any
Registrable Securities pursuant to any effective registration statement.

       3.     Rule 144. The Company shall take all actions reasonably necessary
to enable holders of Registrable Securities to sell such securities without
registration under the Securities Act within the limitation of the exemptions
provided by (i) Rule 144, or (ii) any similar rule or regulation hereafter
adopted by the Commission including, without limiting the generality of the
foregoing, filing on a timely basis all reports required to be filed by the
Exchange Act. Upon the request of the Purchasers, the Company will deliver to
such holder a written statement as to whether it has complied with such
requirements.

       4.     Amendments and Waivers. This Agreement may be amended, modified or
supplemented only by written agreement of the party against whom enforcement of
such amendment, modification or supplement is sought.

       5.     [INTENTIONALLY OMITTED].



                                     - 16 -
<PAGE>   18

       6.     Notice. All notices and other communications hereunder shall be in
writing and, unless otherwise provided herein, shall be deemed to have been
given when received by the party to whom such notice is to be given at its
address set forth below, or such other address for the party as shall be
specified by notice given pursuant hereto:

       (a)    If to the Purchasers, to:

              c/o Forstmann Little & Co.
              767 Fifth Avenue
              New York, NY  10153
              Attention:  Sandra J. Horbach

              With a copy to:

              Fried, Frank, Harris, Shriver & Jacobson
              One New York Plaza
              New York, New York  10004
              Attention:         Robert C. Schwenkel, Esq.

       (b)    If to the Company, to it at:

              NEXTLINK Communications, Inc.
              1505 Farm Credit Drive
              McLean, VA  22102
              Attn:  Gary Begeman, Esq.

              with a copy to:

              Willkie Farr & Gallagher
              787 Seventh Avenue
              New York, NY  10019
              Attn:  Bruce R. Kraus, Esq.

       7.     Assignment; Third Party Beneficiaries. This Agreement shall be
binding upon and inure to the benefit of and be enforceable by the parties
hereto and their respective successors and permitted assigns. This Agreement may
not be assigned by the Company, without the prior written consent of the
Purchasers. The Purchasers may, at their election, at any time or from time to
time, assign their rights under this Agreement, in whole or in part, to any
purchaser or other transferee of shares of Common Stock held by them; provided,
however, that any rights to withdraw shares from inclusion in a registration
statement pursuant to Section 2 shall be made only by the Purchasers for
themselves and all such purchasers and transferees; and provided further, that
no such



                                     - 17 -
<PAGE>   19

assignment will increase the total number of registrations pursuant to Section
2.1 or underwritten offerings the Company is required to effect hereunder.

       8.     Remedies. The parties hereto agree that money damages or other
remedy at law would not be sufficient or adequate remedy for any breach or
violation of, or a default under, this Agreement by them and that, in addition
to all other remedies available to them, each of them shall be entitled to an
injunction restraining such breach, violation or default or threatened breach,
violation or default and to any other equitable relief, including without
limitation specific performance, without bond or other security being required.
In any action or proceeding brought to enforce any provision of this Agreement
(including the indemnification provisions thereof), the successful party shall
be entitled to recover reasonable attorneys' fees in addition to its costs and
expenses and any other available remedy.

       9.     No Inconsistent Agreements. The Company will not, on or after the
date of this Agreement, enter into any agreement with respect to its securities
which is inconsistent with the rights granted to the Purchasers in this
Agreement or otherwise conflicts with the provisions hereof. The Company further
represents and warrants that the rights granted to the Purchasers hereunder do
not in any way conflict with and are not inconsistent with any other agreements
to which the Company is a party or by which it is bound.

       10.    Descriptive Headings. The descriptive headings of the several
sections and paragraphs of this Agreement are inserted for reference only and
shall not control or otherwise affect the meaning hereof.

       11.    Governing Law. This Agreement shall be construed and enforced in
accordance with, and the rights and obligations of the parties hereto shall be
governed by, the laws of the State of New York, without giving effect to the
conflicts of law principles thereof. Each of the parties hereto hereby
irrevocably and unconditionally consents to submit to the exclusive jurisdiction
of the courts of the State of New York and the United States of America located
in the County of New York for any action or proceeding arising out of or
relating to this Agreement and the transactions contemplated hereby (and agrees
not to commence any action or proceeding relating thereto except in such
courts), and further agrees that service of any process, summons, notice or
document by U.S. registered mail to its respective address set forth in Section
6 hereof shall be effective service of process for any action or proceeding
brought against it in any such court. Each of the parties hereto hereby
irrevocably and unconditionally waives any objection to the laying of venue of
any action or proceeding arising out of this Agreement or the transactions
contemplated hereby in the courts of the State of New York or the United States
of America located in the County of New York, and hereby further irrevocably and
unconditionally waives and agrees not to plead or claim in any such court that
any such


                                     - 18 -
<PAGE>   20

action or proceeding brought in any such court has been brought in an
inconvenient forum.

       12.    Counterparts. This Agreement may be executed in any number of
counterparts, each of which shall be deemed an original, but all such
counterparts shall together constitute one and the same instrument.

       13.    Invalidity of Provision. The invalidity or unenforceability of any
provision of this Agreement in any jurisdiction shall not affect the validity or
enforceability of the remainder of this Agreement in that jurisdiction or the
validity or enforceability of this Agreement, including that provision, in any
other jurisdiction. If any restriction or provision of this Agreement is held
unreasonable, unlawful or unenforceable in any respect, such restriction or
provision shall be interpreted, revised or applied in a manner that renders it
lawful and enforceable to the fullest extent possible under law.

       14.    Further Assurances. Each party hereto shall do and perform or
cause to be done and performed all further acts and things and shall execute and
deliver all other agreements, certificates, instruments, and documents as any
other party hereto reasonably may request in order to carry out the intent and
accomplish the purposes of this Agreement and the consummation of the
transactions contemplated hereby.

       15.    Entire Agreement; Effectiveness. This Agreement constitutes the
entire agreement, and supersedes all prior agreements and understandings, oral
and written, between the parties hereto with respect to the subject matter
hereof.





                                     - 19 -
<PAGE>   21



       IN WITNESS WHEREOF, the parties have caused this Agreement to be executed
and delivered by their respective officers thereunto duly authorized.


                              NEXTLINK COMMUNICATIONS, INC.


                              By:   /s/ Gary D. Begeman
                                   -------------------------------------
                                   Name:
                                   Title:



                              FORSTMANN LITTLE & CO.
                              SUBORDINATED DEBT AND EQUITY
                              MANAGEMENT BUYOUT PARTNERSHIP-
                              VII, L.P.

                              By:  FLC XXXIII Partnership
                                   its general partner


                              By:   /s/ Winston W. Hutchins
                                   -------------------------------------
                                   Winston W. Hutchins,
                                   a general partner

                              FORSTMANN LITTLE & CO. EQUITY
                              PARTNERSHIP-VI, L.P.

                              By:  FLC XXXII Partnership, L.P.
                                   its general partner


                              By:   /s/ Winston W. Hutchins
                                   -------------------------------------
                                   Winston W. Hutchins,
                                   a general partner




<PAGE>   22


                                  FL FUND, L.P.

                                  By:       FLC XXXI Partnership, L.P.
                                            its general partner

                                        By:   FLC XXIX Partnership, L.P.
                                              a general partner

                                        By:  /s/ Winston W. Hutchins
                                            -----------------------------------
                                            Winston W. Hutchins,
                                            a general partner