EXECUTION VERSION STOCKHOLDER VOTING AGREEMENT

Exhibit 10.1

EXECUTION VERSION

STOCKHOLDER VOTING AGREEMENT

     THIS STOCKHOLDER VOTING AGREEMENT (this “ Agreement ”) is made and entered into as of November 4, 2005, by and between XO Holdings, Inc., a Delaware corporation (“ Seller ”) and the undersigned stockholder (the “ Stockholder ”).

RECITALS

     WHEREAS, concurrent with the execution and delivery hereof, Seller, XO Communications, Inc., a Delaware corporation (the “Company”) and Elk Associates LLC (“ Buyer ”), a Delaware limited liability company, are entering into an Equity Purchase Agreement of even date herewith (as it may be amended from time to time pursuant to the terms thereof, the “ Purchase Agreement ”), which provides for the sale by the Seller of all of the equity interests in XO Communications, LLC, a Delaware limited liability company and wholly-owned subsidiary of the Seller, constituting substantially all of the assets of the Seller;

     WHEREAS, as of the date hereof, the Stockholder is the record owner of such number of shares of Company Common Stock and Company Preferred Stock as is indicated on Exhibit A to this Agreement, and is also a beneficial owner of such shares for purposes of Rule 13d-3 under the Securities Exchange Act of 1934; and

     WHEREAS, in consideration of the execution and delivery of the Purchase Agreement by the Company and so as to facilitate the consummation of the transactions contemplated by the Purchase Agreement, the Stockholder desires to agree to vote its Shares (as defined below) on the terms and subject to the conditions set forth herein.

     NOW, THEREFORE, in consideration of the foregoing and the mutual covenants and agreements herein, and intending to be legally bound, the parties hereto hereby agree as follows:

     1.  Certain Definitions .

          (a) Capitalized terms used herein without definition are used as defined in the Purchase Agreement, and, in addition:

          “ Board ” means the Board of Directors of the Company.

          “ Company Common Stock ” means the shares of common stock, $0.01 par value per share, of the Company.

          “ Company Preferred Stock ” means the shares of preferred stock, $0.01 par value per share, of the Company designated as 6% Series A Convertible Preferred Stock.

          “ Company Stockholder Approval ” means the adoption by the Stockholder of the Purchase Agreement and the approval of the transactions contemplated thereby or referenced therein, in each case upon the recommendation of the Board and the Special Committee.

          “ Expiration Date ” means the earlier of (i) the day after the Company Stockholder Approval and (ii) the termination of the Purchase Agreement in accordance with its terms.

          “ Exchange Act ” means the Securities Exchange Act of 1934, as amended.

          “ Illiquid Proposal ” means an Alternative Transaction or Competing Proposal that contemplates consideration other than cash or cash equivalents.

          “ Person ” means any individual, corporation, limited liability company, general or limited partnership, unincorporated association, joint venture, or other business enterprise or entity.

          “ Qualifying Superior Proposal ” means a Superior Proposal that (a) is not subject to the satisfaction of the competing bidder or any party providing financing to the bid with the results of any further due diligence investigation of the Company; and (b) is not subject to a financing condition, other than a condition coupled with a commitment letter or commitment letters from a financial institution or financial institutions of recognized standing which themselves contain only customary conditions and are not subject to internal approvals; and provided further that (i) a Competing Proposal shall not be deemed to be a Qualifying Superior Proposal if it contemplates a termination fee of more than 3% of the purchase price provided therein plus actual, reasonable out-of-pocket expenses and (ii) an Alternative Transaction shall not be deemed to be a Qualifying Superior Proposal if it contemplates a termination fee of more than 3% of the purchase price provided therein, unless the offer contemplates a bid of at least $75 million more than the highest outstanding bid, but in any event the termination fee shall be no more than 4% of the purchase price provided therein.

          “ Shares ” means (i) all shares of Company Common Stock, Company Preferred Stock and other voting securities of Company owned, beneficially or of record, by the Stockholder as of the date hereof, (ii) all additional shares of Company Common Stock, Company Preferred Stock and other voting securities of Company acquired by the Stockholder, beneficially or of record, during the period commencing with the execution and delivery of this Agreement and expiring on the Expiration Date, and (iii) such other shares of Company Common Stock, Company Preferred Stock and other voting securities of Company over which the Stockholder has or will have voting power during the period commencing with the execution and delivery of this Agreement and expiring on the Expiration Date.

          “ Special Committee ” means that special committee of the Board appointed on April 22, 2005.

          (b) Any singular term in this Agreement shall be deemed to include the plural, and any plural term the singular. Whenever the words “include,” “includes” or “including” are used in this Agreement, they shall be deemed followed by the words “without limitation.”

          (c) Defined terms used herein but not otherwise defined herein have the meaning set forth in the Purchase Agreement.

     2.  Transfer of Voting Rights . At all times during the period commencing with the execution and delivery of this Agreement and expiring on the Expiration Date, the Stockholder shall not deposit (or permit the deposit of) any Shares in a voting trust or grant any proxy or enter into any voting agreement or similar agreement in contravention of the obligations of the Stockholder under this Agreement with respect to any of the Shares.

     3.  Agreement to Vote Shares . The Stockholder hereby agrees that, until this Agreement is terminated pursuant to Section 6 hereof, at any meeting of the holders of Shares (including a decision by written consent), however called, and at every adjournment or postponement thereof, the Stockholder shall:

          (a) appear at the meeting or otherwise cause the Shares to be counted as present thereat for purposes of establishing a quorum;

          (b) subject to Section 3(d) hereof, vote the Shares or cause the Shares to be voted at the Stockholders’ Meeting called for the purpose of voting on the Purchase Agreement and the transactions contemplated thereby, or execute consents or cause such consents to be executed in respect of the Shares when requested to execute such consents by the Special Committee for the purpose of voting for the Purchase Agreement and the transactions contemplated thereby, in respect thereof, in favor of the adoption by the Seller’s stockholders of the Purchase Agreement and the approval of the transactions contemplated thereby, including any action necessary to effectuate the Restructuring Merger, waive any dissenter or appraisal right it may have in respect of such transaction and any action required in furtherance thereof;

          (c) subject to 3(d) hereof, vote, or execute consents in respect of the Shares, or cause t