Exhibit 10.4 ------------ AMENDMENT TO REGISTRATION RIGHTS AGREEMENT ------------------------------------------ THIS AMENDMENT TO REGISTRATION RIGHTS AGREEMENT is dated as of April 26, 1999 by and between NEXTLINK Communications, Inc., a Delaware corporation (the "Company"), and the persons and entities that have executed and delivered the Consent and Indemnity Agreement of Stockholders in the form attached to the Merger Agreement (as defined below) (the "Holders") by and through the execution of the Registration Rights Agreement (as defined below) by Thomas H. Jones (the "Stockholders' Representative") as their attorney-in-fact. Capitalized terms used herein without definition have the meanings assigned to them in the Registration Rights Agreement referenced below. RECITALS WHEREAS, pursuant to the terms of an Agreement and Plan of Merger, dated as of January 14, 1999 by and among the Company, WNP Communications, Inc. and PCO Acquisition Corp. (the "Merger Agreement"), the Company and the Holders are parties to a Registration Rights Agreement, dated as of January 14, 1999 (the "Registration Rights Agreement"); and WHEREAS, the parties desire to make certain amendments to the Registration Rights Agreement. NOW, THEREFORE, for good and valuable consideration, the receipt and sufficiency of which are hereby acknowled ged, the parties agree as follows: I. Amendments to the Registration Rights Agreement. ------------------------------------------------ A. Section 2(a) of the Registration Rights Agreement is hereby replaced in its entirety with the following: "a. Resale at Closing. The Company will use reasonable best efforts to have that number of shares of Common Stock issued at the Closing, having an aggregate market value of approximately $175 million (all references to the market value of Common Stock in this Agreement to be determined based on the Closing Date Average Price), subject to adjustment as set forth below (as so adjusted, the "WNP Amount"), registered under the Securities Act for resale by the Holders in an underwritten offering (the "Initial Offering") pursuant to a registration statement (the "Initial Registration Statement") that has been declared effective by the Commission within 30 days following the Closing, which registration statement shall be kept effective by the Company until the earlier of such time as the Initial Offering is completed or the expiration of 60 days following the effectiveness of the Initial Registration Statement. Each Holder and its permitted assignees shall be entitled to sell in the Initial Offering that number of shares of Common Stock it receives in the Merger equal to its pro rata share of the Common Stock issued at the Closing multiplied by the WNP Amount. Any Holder or its permitted assignees wishing to sell shares in the Initial Offering shall deliver or cause the Stockholders' Representative to deliver on its behalf notice to the Company, which notice shall become irrevocable at 12:00 noon (New York time) on April 29, 1999 (and which notice, if oral, shall be confirmed in writing on the same day) specifying the maximum number of shares such Holder or assignee wishes to sell in such offering. If any Holder or assignee elects to sell less than its pro rata share, the number of shares permitted to be sold by all other participating Holders or their permitted assignees will be increased pro rata by the number of shares that would otherwise have been allotted to non-participating or partially participating Holders or their permitted assignees; provided however, that with respect to any Holder which distributes shares to its beneficial owners following the Closing, such reallotment shall be applied first within such group of beneficial owners; and provided further, that with respect to any two or more Holders who are "affiliates" of one another within the meaning of Rule 144 under the Securities Act, such reallotment shall be applied first among such affiliated Holders. Each Holder acknowledges and agrees that the Company may elect to include additional shares of Common Stock having an aggregate market value of approximately $165 million for its own account in the Initial Registration Statement and the Initial Offering, and may be required to include additional shares pursuant to registration rights agreements heretofore furnished to WNP. In the event that the aggregate market value of Common Stock offered for the account of the Company in the Initial Offering exceeds $165 million, the WNP Amount shall be increased by an amount equal to one third of such excess. All shares offered in the Initial Offering shall be subject to the provisions of subdivision (g) below." B. Section 2(g)(i) of the Registration Rights Agreement is hereby replaced in its entirety with the following language: "(i) In the case of the Initial Offering, the securities sought to be included in such offering by the Holders shall be excluded as follows: (A) first, securities offered for the account of the Company and the Holders or their permitted assignees as described in the penultimate sentence of Section 2(a) above shall be excluded on a pro rata basis with securities sought to be included in the Initial Offering by all other Persons seeking inclusion of securities in such offering (including pursuant to so-called piggyback registration rights), until the aggregate market value of the securities sought to be included in such offering by the Company has been reduced to approximately $165 million (as pertains to the shares of the Company and the Holders or their permitted assigns, such exclusions shall be based upon the Holders' and the Company's relative number of securities sought to be so included pursuant to the penultimate sentence of Section 2(a)); (B) thereafter, the number of shares of Common Stock sought to be included by the Holders shall be excluded on a pro rata basis with securities sought to be included in the Initial Offering by the Company and all other Persons seeking inclusion of securities in such offering (including pursuant to so-called piggyback registration rights), based upon the Holders', the Company's and the other Persons' relative number of securities sought to be so included until the aggregate market value of the securities sought to be included in such offering by the Holders has been reduced to approximately $125 million; (C) thereafter, any additional securities required to be excluded from such offering in order to comply with the advice of the managing underwriter shall be securities that were to have been offered for the Company's account until the offering includes no such securities; and (D) thereafter, the securities sought to be included in such offering by the Holders shall be excluded on a pro rata basis with the securities sought to be included in the Initial Offering by all other Persons seeking inclusion of securities in such offering (including pursuant to so-called piggyback registration rights), based upon the Holders' and the other Persons' relative number of securities sought to be so included. C. Section 4(c) of the Registration Rights Agreement is hereby replaced in its entirety with the following language: "c. Holdback Agreements. Each Holder agrees, if required by the managing underwriter in any underwritten public offering of securities pursuant to the Initial Registration Statement, a Subsequent Registration Statement or an Incidental Registration Statement, not to effect any public sale or public distribution of Registrable Securities, any sale or distribution thereof pursuant to Rule 144 or 145 under the Securities Act, or any short sale thereof or any transaction or series of transactions having a substantially similar economic effect (other than (i) sales pursuant to the Initial Registration Statement, or (ii) distributions to any stockholder, partner or other beneficial owner of such Holder) during the period beginning, in the case of the Initial Registration Statement, on the date hereof and, in the case of each Subsequent and Incidental Registration, beginning seven days prior to the effective date of such registration statement, and ending on the date 90 days after the Initial Registration Statement, any Subsequent Registration Statement or any Incidental Registration Statement shall have been declared effective, provided that in the event the Initial Registration Statement shall not have been declared effective within 30 days following the Closing Date and a majority-in-interest of the Holders seeking to participate in the Initial Offering shall have voted to be released, in whole or in part, from such restrictions, all of the Holders shall be released, in whole or in part, as so determined, from such restrictions with respect to the Initial Offering. In addition, if (i) the market value of the Common Stock of the Holders included in the Initial Offering is limited to $150 million or less and a majority-in-interest of the Holders seeking to participate in such offering vote to be released, in whole or in part, from the restrictions contained in the preceding sentence or (ii) the market value of Common Stock of the Holders included in any Subsequent Offering is limited to $30 million or less and a majority-in-interest of all Holders of Registrable Securities vote to be released, in whole or in part, from the restrictions contained in the preceding sentence then all Holders shall be released from the restrictions contained in the preceding sentence with respect to such offering, in whole or in part, as so determined." II. No Further Amendments. Except as specifically amended hereby, the Registration Rights Agreement shall remain unmodified and in full force and effect and is hereby reaffirmed. III. Miscellaneous. ------------- A. This Amendment to Registration Rights Agreement shall be governed by and construed in accordance with the laws of the State of Delaware. B. This Amendment to Registration Rights Agreement may be executed by the parties hereto in several counterparts hereof and by the different parties hereto on separate counterparts hereof, all of which counterparts shall together constitute one and the same agreement. IN WITNESS WHEREOF, the Company and the Holders have caused this Amendment to Registration Rights Agreement to be signed and delivered by their respective duly authorized officers or representatives, as applicable, as of the date first above written. NEXTLINK COMMUNICATIONS, INC. By: /s/ R. Bruce Easter, Jr. ---------------------------- Name: R. Bruce Easter, Jr. Title: Vice President HOLDERS /s/ Thomas H. Jones -------------------------------- By: Thomas H. Jones, as Stockholders' Representative