Document:

<PAGE>

                                                                   Exhibit 10.20

               CERTAIN PORTIONS OF THIS EXHIBIT HAVE BEEN OMITTED
                 BASED ON A REQUEST FOR CONFIDENTIAL TREATMENT

                  OMITTED PORTIONS HAVE BEEN SEPARATELY FILED
                  WITH THE SECURITIES AND EXCHANGE COMMISSION

                      MEDIA GATEWAY SERVICES AGREEMENT III

          This Media Gateway Services Agreement (the "Agreement") between KMC
Telecom VI Inc., a Delaware corporation whose address is 1545 Route 206, Suite
300, Bedminster, NJ 07921 (collectively, "KMC") and Qwest Communications
Corporation, a Delaware corporation whose address is 700 Qwest Tower, 555
Seventeenth Street, Denver, Colorado  80202 ("Qwest"), is effective as of June
30, 2000 (the "Effective Date").

          WHEREAS, Qwest desires to purchase KMC's MGS Services on an MGS
Circuit basis (as defined below) and KMC desires to provide the MGS Services to
Qwest, pursuant to the rates, terms, and conditions of this Agreement; and

          WHEREAS, KMC and Qwest wish to set forth the terms and conditions
under which Qwest is willing to purchase and KMC is willing to provide MGS
Services to Qwest.

          NOW, THEREFORE, in consideration of the mutual promises, covenants,
and other terms and conditions contained herein, and other good and valuable
consideration, the receipt and sufficiency of which are hereby acknowledged, the
parties agree as follows:

          Definitions:  The following capitalized terms shall have the meanings
          ------------
specified as follows:

          "MGS Circuit" means a DS0-level circuit individually ordered by Qwest
           -----------
and provided by KMC to allow data or voice dial-up users, through SS7 trunks, to
connect to the Qwest IP network via KMC's Media Gateway servers (each, an "MGS
Server").

          "MGS Services" means the provision, operation and maintenance of MGS
           ------------
Servers, operated by KMC on a dedicated basis for Qwest (including the
maintenance of hardware, equipment, environmental control, network connections,
and line provisioning) that provide connectivity  between the Qwest data network
access connection ("DNAC") at the KMC POP and the public switched telephone
network ("PSTN") for Qwest's end users, through individually-ordered MGS
Circuits using KMC's own connection to the public switched telephone network.
For each MGS Circuit ordered by Qwest, MGS Services will be provided.

          "POP" means the point of presence operated by one party at which data
           ---
(and other telecommunications) traffic is exchanged.

                                       1
<PAGE>

     1.   Incorporation of Recitals.  The foregoing recitals are hereby
incorporated in this Agreement and made a part hereof to the same extent as if
herein set forth in full.

     2.   MGS Services.  KMC will provide the MGS Services to Qwest and Qwest's
          end users according to the Service Levels defined and specified in
          Schedule 2 to this Agreement.  KMC shall provide the MGS Services for
          the term set forth in Section 7.a. below.  Qwest, at its sole cost,
          shall establish and manage (i) a designated DNAC to KMC's network at
          each location that KMC provides the MGS Services and (ii) an access
          link between the DNAC and Qwest's POP.  KMC will be responsible for
          the physical installation of the DNAC at the KMC POP and the testing
          and activation of MGS Circuits.  KMC shall be responsible for all
          operation, maintenance, installation, and network line connections for
          the MGS Services, subject to Qwest's obligations as set forth below.
          Notwithstanding the foregoing,  Qwest shall have the ability to
          conduct remote monitoring, software configuration and billing
          functions for its end user customers using Qwest software and network
          management equipment related to the MGS Services, including software
          programming related to the MGS Servers as necessary.  Qwest shall
          conduct remote monitoring of the MGS Servers, provide traffic and
          utilization information to KMC on a regular basis and notify KMC of
          the need to make onsite corrections of errors or defects, which KMC
          shall do promptly in accordance with the Service Levels set forth in
          Schedule 2.  In order to assist Qwest in ordering MGS Services and
          otherwise fulfilling its obligations under this Section, KMC will,
          upon Qwest's request, provide Qwest with all necessary information in
          KMC's possession and assistance relating to the establishment and
          maintenance of DNACs and the MGS Circuits, including but not limited
          to providing software specifications, documentation, network
          provisioning information, network routing maps and traffic and
          performance reports as it relates to the KMC network.  All such
          information and materials provided by KMC will be the confidential
          information of KMC.  The parties may enter into additional mutually-
          acceptable agreements in separate writings or as written amendments
          hereto, under which KMC will provide technical testing and activation
          of the network connections on the Qwest side of the network
          demarcation (including testing of the Qwest-operated remote software,
          network management tools and software configuration).

     3.   Rates.

          a.   Qwest shall pay KMC for MGS Services according to the prices for
               MGS Circuits as set forth in Schedule 1 to this Agreement (the
               "MGS Circuit Rates"). Charges for the MGS Circuits will be as
               follows: (a) on [text deleted] Qwest shall commence payment on a
                               --------------
               monthly basis for the [text deleted] of (x) [text deleted] of all
                                     ---------------       --------------
               MGS Circuits deemed installed (as described below) or (y) the

               [text deleted] of MGS Circuits in service plus all out of pocket
               ---------------
               and third party costs incurred by KMC and payable by Qwest
               pursuant to Appendix A to Schedule 1 for [text deleted] of all
                                                        ---------------

                                       2
<PAGE>

               MGS Circuits deemed installed ("Out of Pocket Costs"); (b) on
               [text deleted] Qwest shall commence monthly payments for the
               --------------
               [text deleted]  of (x) [text deleted] of all MGS Circuits deemed
               ---------------        --------------
               installed or (y) the [text deleted] of MGS Circuits in service
                                    ---------------
               plus [text deleted] of all Out of Pocket Costs not previously
                    ---------------
               paid by Qwest; (c) on [text deleted] Qwest shall commence monthly
                                     --------------
               payments for the [text deleted]  of (x) [text deleted] of all MGS
                                ---------------        --------------
               Circuits deemed installed or (y) the [text deleted] of MGS
                                                    ---------------
               circuits in service plus [text deleted] of all Out of Pocket
                                        ---------------
               Costs not previously paid by Qwest, and (d) on [text deleted]
                                                              --------------
               Qwest shall commence payment for all MGS Circuits deemed
               installed.

          b.   An MGS Circuit will be deemed installed as of the earlier of (a)
               the day that is the later of (i) the date when KMC notifies Qwest
               that it has installed the MGS Circuit or (ii) 60 days after the
               date when KMC orders the corresponding [text deleted] from the
                                                      --------------
               incumbent local exchange carrier ("ILEC"); or (b) [text deleted]
                                                                 --------------
               days after the Effective Date (or, in the case of an additional
               MGS Circuit ordered pursuant to Section 6 hereof, [text deleted]
                                                                 --------------
               days after the acceptance of the Service Order by KMC).  Qwest
               will be charged the MGS Circuit Rates pro rated for any partial
               first month.

          c.   Payments for the MGS Services/MGS Circuits shall be due and
               payable within [text deleted] days after receipt of KMC's
                              ---------------
               invoice, except to the extent Qwest in good faith disputes any
               portion of the charges; provided that Qwest may not withhold
               payment of amounts in dispute to the extent such amounts exceed

               [text deleted] of the invoice amount; provided further that such
               --------------
               [text deleted] limit shall not apply to disputes arising from
               --------------
               KMC's failure to correctly apply credits (including MGS Circuit
               Delay Credits) or from KMC invoicing for MGS Circuits prior to
               the date they are deemed installed, as set forth above. In the
               event of such a dispute, Qwest shall pay the undisputed portion
               of the charges on the invoice (as well as amounts in dispute to
               the extent they are subject to, and exceed, the [text deleted]
                                                               --------------
               limit set forth above) and the parties shall cooperate to resolve
               the dispute as provided in this Agreement.  The parties shall use
               reasonable efforts to resolve such dispute within [text deleted]
                                                                 --------------
               days.  If the dispute is resolved in favor of Qwest and Qwest has
               withheld the disputed amount, no interest credits or penalties
               will apply.  If the dispute is resolved in favor of Qwest and
               Qwest has paid the disputed amount, Qwest will be credited with
               interest on such amount by KMC at the lesser of the rate of one
               and one-half percent (1 1/2%) per month or the maximum rate
               permitted by law, from the date KMC received payment up to and
               including the date of refund.  If the dispute is resolved in
               favor of KMC and Qwest has paid the disputed amount on or before
               the payment due date, no interest credit or penalties will apply.
               If the dispute is resolved in favor of KMC and Qwest has withheld
               the disputed amount, any payments

                                       3
<PAGE>

               withheld pending settlement of the disputed amount shall bear
               interest at the lesser of the rate of one and one-half percent
               (1 1/2%) per month or the maximum rate permitted by law, from the
               payment due date up to and including the date of payment.

          d.   The MGS Circuit Rates are payable by Qwest without regard to any
               taxes, including sales taxes if applicable, FCC charges, or other
               third party costs imposed with respect to the MGS Circuits, which
               taxes, charges and other costs, (other than taxes based on KMC's
               net income) shall be born solely by Qwest. No adjustment shall be
               made to the MGS Circuit Rates on account of taxes or other items
               imposed on Qwest in connection with the MGS Circuits.

          e.   In the event of an MGS Circuit Delay (as defined below) and
               payment for such MGS Circuit would otherwise be due in accordance
               with Section 3 a., KMC shall provide to Qwest for each affected
               MGS Circuit an MGS Circuit Delay Credit equal to the product of
               (A) [text deleted] of the [text deleted] for the affected MGS
                   --------------        --------------
               Circuit times (B) the [text deleted] of [text deleted] of such
                                     --------------    ------------------
               MGS Circuit Delay.  Notwithstanding the provisions of Section
               10(a), acceptance of the credit by Qwest pursuant hereto shall
               constitute Qwest's sole remedy for an MGS Circuit Delay.

          f.   An "MGS Circuit Delay" shall be deemed to occur if, (x) after the
               date upon which an MGS Circuit is deemed installed as set forth
               above, Qwest notifies KMC that it has an actual customer to whom
               it desires to provide service using such MGS Circuit and within
               [text deleted] days after such notice KMC has not completed
               ---------------
               existing testing and circuit hand-off procedures (and other such
               procedures as mutually agreed by the parties) with respect to
               such MGS Circuit, including the verification of full connectivity
               through the DNAC to Qwest's IP network; provided, however, that
               notwithstanding the testing and connectivity requirements set
               forth in this sentence, an MGS Circuit Delay shall not have
               occurred, and monthly charges for the MGS Circuit shall commence
               or continue as prescribed in Section 3.a, if due to an act or
               omission of Qwest in the provision of services or equipment
               reasonably necessary for KMC to satisfy its testing and
               connectivity obligations set forth herein, KMC is unable to
               satisfy such obligations.

          g.   Qwest agrees that, except (i) as otherwise expressly provided in
               Section 3.c with respect to (x) disputed amounts not exceeding
               [text deleted] of the amount invoiced by KMC pursuant to Section
               --------------
               3.a, (y) disputes arising from KMC's failure to correctly apply
               credits  as described in Section 3.c or (z) KMC invoicing for MGS
               Circuits prior to the date they are deemed installed; (ii) during
               the continuance of an Event of Default described in Section
               10.a.i and (iii) as otherwise expressly provided in Section 9.b
               or

                                       4
<PAGE>

               14, Qwest's obligations to make all payments payable by it under
               this Agreement in accordance with the terms of this Agreement and
               the Acknowledgement and Consent Agreement attached hereto as
               Exhibit A are absolute and unconditional and that it will make
               all payments payable by it hereunder regardless of set- off,
               recoupment, abatement or other similar right, existing or future,
               which Qwest may have against KMC.

     4.   Services Commitment. Qwest will purchase MGS Services in at least the
          quantities set forth in the Implementation Schedule attached hereto as
          Schedule 3 (the "Services Commitment") on or before November 1, 2000
          (the "Commitment Date") unless this Agreement is terminated pursuant
          to Section 7.b or pursuant to Sections 10, 14, or 16 before the
          Commitment Date, in which case Qwest shall have no obligation with
          respect to the Services Commitment (except for MGS Services actually
          rendered and, if applicable, the early termination charge set forth in
          Section 7.b).  This Agreement includes the terms, conditions, Service
          Level commitments, technology and MGS Circuit Rates for the MGS
          Circuits/MGS Services within the Services Commitment, as well as
          additional MGS Circuits/MGS Services that may be ordered pursuant
          hereto.

     5.   Implementation Schedules and Growth Forecast.

          MGS Circuits sufficient to satisfy the Services Commitment shall be
          installed pursuant to the Implementation Schedule set forth in
          Schedule 3 hereto.  In the event KMC is unable to (except to the
          extent such inability results from any acts or omissions of Qwest), or
          the parties otherwise agree that KMC shall not install such MGS
          Circuits before the Commitment Date, Qwest will nonetheless be deemed
          to have satisfied the Services Commitment and no shortfall penalty
          shall be owed by Qwest to KMC with respect to same.  Qwest
          acknowledges that KMC may not agree to defer the installation of MGS
          Circuits without first obtaining the consent of a Financing Source (as
          defined in Section 16(b)) and KMC has no obligation hereunder to
          obtain such consent.

     6.   Equipment Configuration.  KMC shall provide MGS Services other than
          those in the Implementation Schedule after receipt of a Qwest service
          order in a form mutually agreed by the parties (each a "Service
          Order") for such MGS Services; provided, however, that any Service
          Order shall not be binding until accepted by KMC and in the event KMC
          in its discretion determines that filling such order would require
          additional third party capital financing, such Service Order shall be
          subject to obtaining such additional third party capital financing,
          and the provision of MGS Services pursuant thereto may be conditioned
          on the agreement of both parties to a separate agreement governing
          such MGS Services.  Such Service Order shall specify a requested
          installation date that is at least 90 days after the date of such
          Service Order.  KMC shall notify Qwest within 2 business days after
          receipt of a Service Order if such Service Order contains insufficient
          information for KMC to meet the requested provisioning period.  In
          filling Service Orders,

                                       5
<PAGE>

          KMC shall use modems, MGS Servers and other network equipment
          (according to a configuration of cabinets, fuse panels, racks,
          routers, and other equipment necessary for a plug and play
          configuration) that are specified by Qwest in each Service Order. The
          MGS Service will initially be provided using Cisco or Nortel equipment
          (as agreed to by Qwest) (together with equipment specified by Qwest
          pursuant to the next to last sentence of this Section 6, the
          "Qwest-Required Equipment") which enables Qwest to exchange either
          data (e.g. V.90), voice (e.g. G.711) or fax (e.g. T.37) traffic with
          end user customers (i.e. the dial-up users) of the MGS Services.
          Except with respect to MGS Circuits that must be ordered to satisfy
          the Services Commitments, Qwest may specify other models or vendors of
          equipment to be used in the MGS Services configuration, provided that
          Qwest shall be responsible for and shall pay any increased costs to
          KMC resulting from the use by KMC of other models and vendors of MGS
          Servers at Qwest's request. Qwest may also request that software
          upgrades be made; provided that Qwest shall be responsible for and
          shall pay any increased costs to KMC resulting from such software
          upgrades; provided further that absent such request and payment by
          Qwest, KMC shall be under no obligation to upgrade any software. Each
          Service Order is hereby incorporated by reference.

     7.   Term, Early Termination Charge.

          a.   This Agreement shall have an initial term commencing on the
               Effective Date and ending forty-two (42) months after February 1,
               2001, unless earlier terminated pursuant to Section 9.b.,10, 14,
               or 16.  Each of the MGS Circuits listed in the Implementation
               Schedule shall have a term that is forty-two (42) months after
               February 1, 2001, but shall continue at the option of Qwest for
               an additional term to be specified in writing by Qwest no later
               than 30 days prior to the expiration of the initial term. Each
               additional MGS Circuit provided pursuant to Section 6 shall have
               a term beginning on the date it is deemed installed as described
               in Section 3 b. and ending forty-two (42) months thereafter,
               unless earlier terminated pursuant to Section 9.b.i, 9.b.ii, 10,
               14, or 16 or extended by Qwest in the manner described in the
               immediately preceding sentence.  In the event the term of one or
               more such MGS Circuits extends beyond the expiration of the
               initial term as set forth above, the terms and conditions of this
               Agreement shall continue to apply to each such additional MGS
               Circuit until the expiration of the term of each such MGS
               Circuit.  Following expiration of the initial term of this
               Agreement, the term shall automatically renew for successive
               twelve month terms unless either party notifies the other party
               of its intent not to renew at least thirty (30) days prior to the
               end of the initial term or renewal term, as the case may be.

          b.   In the event Qwest terminates or cancels MGS Services for an MGS
               Circuit, or this Agreement, [text deleted] then Qwest shall be
                                           ---------------
               responsible for paying KMC an early termination charge equal to
               one hundred percent

                                       6
<PAGE>

               (100%) of the MGS Circuit Rates for the canceled MGS Circuit(s),
               multiplied by the number of full months remaining in the term at
               the time of cancellation. Any termination of this Agreement as
               described in the immediately preceding sentence shall not be
               effective until the early termination charge due pursuant to the
               immediately preceding sentence has been paid in full.

     8.   Insurance.

          a.   During the term of this Agreement, KMC shall maintain insurance
               of the kinds and in the amounts specified below with insurers of
               recognized responsibility, licensed to do business in the
               State(s) where the MGS Services are being performed, and having
               either: an A.M Best's rating of A8, a Standard & Poor's ("S&P's")
               rating of AA, or a Moody's rating of AaZ.  If any MGS Services
               provided for or to be performed under this Agreement are
               subcontracted, KMC shall require the subcontractor(s) to maintain
               and furnish it with insurance approved by Qwest.

          b.   In accordance with the above, KMC and any subcontractors shall
               maintain the insurance coverage in accordance with that certain
               Access Service Agreement  between KMC and certain of its
               affiliates and Qwest dated as of December 15, 1998, as such may
               be amended from time to time pursuant to the terms thereof.

          c.   Should KMC at any time neglect or refuse or provide the insurance
               required, or should such insurance be canceled or non-renewed,
               Qwest shall have the right to purchase such insurance, and the
               cost shall be billed to KMC.  In addition, should KMC at any time
               neglect or refuse to pay the necessary premium, Qwest shall have
               the right to pay same and deduct the amount therefor from monies
               due KMC.

          d.   KMC and all subcontractors shall comply with the terms of the
               Occupational Safety and Health Administration (OSHA) and all
               locations, jurisdictions' safety and health regulations during
               the full term of this Agreement.

     9.   Representations and Warranties.

          a.   Each party represents and warrants to the other that it has the
               power and authority to enter into this Agreement including each
               Schedule, Attachment and Exhibit hereunder.

          b.   KMC represents, warrants and agrees that:

                                       7
<PAGE>

               i.   it will provide, to Qwest and its end user customers, MGS
                    Services that meet or exceed the Service Levels described in
                    Schedule 2.  Should KMC, in any [text deleted] during any
                                                    --------------
                    consecutive [text deleted] period, (x) fail to provide the
                                --------------
                    MGS Services at the Service Levels defined in item 1 (v) of
                    Schedule 2 for [text deleted] of the MGS Circuits in a
                                   --------------
                    particular Market Area;  or (y) fail to meet the Service
                    Level set forth in item 1 (iii) of Schedule 2 for Qwest
                    calls affecting, in the aggregate, more than [text deleted]
                                                                 --------------
                    of the MGS Circuits in a particular Market Area; or (z) fail
                    to meet the Service Level set forth in item 1 (ii) of
                    Schedule 2 in a particular Market Area (unless, in any of
                    such events, such failure was substantially caused by a
                    force majeure event, Qwest-Required Equipment or an action
                    or omission of Qwest, its equipment or its agents or
                    employees), Qwest shall be entitled to terminate all MGS
                    Circuits in such Market Area without any liability to KMC
                    except for payment due for services provided up to the point
                    of termination, by providing written notice to KMC within
                    sixty (60) days after the occurrence of the events giving
                    rise to Qwest's right to terminate such Market Area;
                    provided that, within ten (10) business days after the end
                    of any calendar month in which such failure of MGS Circuits
                    to meet such standards has occurred, Qwest shall give KMC
                    written notice of such failure and provide to KMC all
                    information within Qwest's possession that is reasonably
                    calculated to assist KMC in taking steps to prevent the
                    recurrence of such failure.  If, during the term of this
                    Agreement, Qwest shall become entitled to terminate all MGS
                    Circuits in any three or more Market Areas that contain in
                    the aggregate [text deleted] or more of the MGS Circuits to
                                  ---------------
                    be provided hereunder, Qwest shall be entitled to terminate
                    this Agreement in its entirety by providing written notice
                    to KMC within sixty (60) days after the occurrence of the
                    events giving rise to Qwest's right to terminate this
                    Agreement, provided Qwest has provided KMC with reasonable
                    notice of KMC's failure to meet Service Levels under this
                    Agreement.  Notwithstanding the provisions of Section 10.a,
                    termination of Market Areas and/or this Agreement for breach
                    of this Service Level warranty pursuant to this Section
                    9.b.i shall be Qwest's sole remedy for breach of this
                    Agreement for failure of KMC to meet Service Levels in
                    accordance with this Section 9.b.i, and such termination
                    shall be effective (without penalty) thirty (30) days after
                    KMC receives notice of the breach of this warranty and
                    intent to terminate from Qwest.  For purposes of this
                    Section 9.b.i, a "Market Area" means the market being served
                    by a single aggregation point for MGS Servers;

                                       8
<PAGE>

                ii. In the event an MGS Circuit is interrupted continuously
                    for a period of [text deleted] or incurs cumulative outages
                                    --------------
                    of over [text deleted] in any [text deleted] period, Qwest
                            --------------        --------------
                    shall be entitled, at its sole option, to either (but not
                    both) of the following: (i) a credit to Qwest's account for
                    the [text deleted] for [text deleted] of MGS Services for
                        --------------     --------------
                    every [text deleted] continuous interruption of the MGS
                          --------------
                    Services up to total credits equal to [text deleted] for
                                                          --------------
                    [text deleted] of MGS Services in each [text deleted] for
                    --------------                         --------------
                    each MGS Circuit; or (ii) the termination of the affected
                    MGS Circuits, provided such interruption(s) was not
                    substantially caused by an event of force majeure, or an
                    action or omission of Qwest, its equipment or its agents or
                    employees.  Termination of any particular MGS Circuits or
                    MGS Services under this Section shall not serve to terminate
                    any other MGS Circuits or MGS Services and any exercise of
                    Qwest's rights under this Section shall not (x) reduce or
                    otherwise affect Qwest's rights to termination of this
                    Agreement for Service Level failures under Section 9.b.i; or
                    (y) affect the number of MGS Circuits for which MGS Services
                    have been ordered with respect to Services Commitments (i.e.
                    the number of MGS Circuits for which MGS Services have been
                    ordered will not be reduced in determining whether Qwest has
                    met the Services Commitments if MGS Circuits are terminated
                    pursuant to this Section); provided that with the exception
                    of (x) and (y) above, notwithstanding the provisions of
                    Section 10(a), acceptance of a credit pursuant to (i) above
                    or termination of affected MGS Circuit(s) pursuant to (ii)
                    above shall be Qwest's sole remedy for the interruptions
                    described in this Section 9.b.ii;

               iii. to the best of its knowledge, there are no pending or
                    threatened lawsuits, claims, disputes or actions (a)
                    alleging that the Equipment infringes or misappropriates any
                    third party's patent, copyright, trademark, trade secret,
                    proprietary or other intellectual property rights, or (b)
                    adversely affecting the Equipment, the MGS Services or KMC's
                    ability to undertake and perform its obligations under this
                    Agreement; and

                iv. it has and will maintain manufacturer's warranties of the
                    kind typically used in the applicable industry for all
                    Equipment used to provide the MGS Services and will pass on
                    the benefits of such warranties to the full extent possible
                    to Qwest for the MGS Services.

          c.   THE EXPRESS WARRANTIES IN THIS AGREEMENT ARE IN LIEU OF ALL OTHER
               WARRANTIES, EXPRESS OR IMPLIED, INCLUDING, BUT NOT LIMITED TO,
               THOSE OF

                                       9
<PAGE>

               MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.

     10.  Default/Termination.  This Agreement and any MGS Services can be
          terminated only as provided in Sections 9.b.i, 9b.ii, 14, 16, and this
          Section 10.

          a.    i.  Qwest may terminate this Agreement if any one of the
                    following occur (each, an "Event of Default"): (i) if KMC
                    becomes insolvent or admits in writing its inability to pay
                    debts as they mature, or makes an assignment for the benefit
                    of creditors and as a result thereof KMC fails to meet the
                    requirements of Section 9.b.i or 9.b.ii; (ii) if a petition
                    under any foreign, state or United States bankruptcy act,
                    receivership statute, or the like, as they now exist, or as
                    they may be amended, is filed by KMC and as a result thereof
                    KMC fails to meet the requirements of Section 9.b.i or
                    9.b.ii; or (iii) if such a petition is filed against KMC by
                    any third party and such application is not resolved
                    favorably to such other party within sixty (60) days and as
                    a result thereof KMC fails to meet the requirements of
                    Section 9.b.i or 9.b.ii.

               ii.  KMC may terminate this Agreement if any one of the following
                    occur (each, an "Event of Default"): (i) if Qwest fails to
                    pay any amount due to KMC within fifteen (15) business days
                    of demand of such overdue amount by KMC (or, in the case of
                    disputed amounts withheld by Qwest pursuant to Section 3.c,
                    within fifteen (15) business days after the dispute as to
                    such amounts is resolved in KMC's favor); (ii) if Qwest
                    becomes insolvent or admits in writing its inability to pay
                    debts as they mature, or makes an assignment for the benefit
                    of creditors and as a result thereof Qwest fails to timely
                    pay KMC in accordance with the terms of this agreement;
                    (iii) if a petition under any foreign, state or United
                    States bankruptcy act, receivership statute, or the like, as
                    they now exist, or as they may be amended, is filed by Qwest
                    and as a result thereof Qwest fails to timely pay KMC in
                    accordance with the terms of this agreement; or (iv) if such
                    a petition is filed against Qwest by any third party and
                    such application is not resolved favorably to such other
                    party within sixty (60) days and as a result thereof Qwest
                    fails to timely pay KMC in accordance with the terms of this
                    agreement.

          b.        The parties acknowledge that this Agreement may be subject
                    to the approval of public utility commissions of individual
                    states or other regulatory agencies wherein MGS Services are
                    provided. Either party shall have the right to terminate the
                    affected MGS Service without liability except for MGS
                    Services actually rendered if, by a final, non-appealable
                    order of a court of competent jurisdiction, the Federal

                                       10
<PAGE>

               Communications Commission, or other local, state or federal
               government authority, (i) KMC is prohibited from furnishing the
               MGS Services; or (ii) any material rate or term contained herein
               is substantially changed in a manner that is materially adverse
               to the terminating party.

     11.  Indemnification for Infringement.

          a.   The following indemnification provisions set forth the entire
               obligation of KMC with respect to infringement of proprietary
               rights arising directly from the Qwest-Required Equipment used to
               provide MGS Services; provided, however, notwithstanding the
               foregoing, that KMC shall have no indemnification or other
               obligation to Qwest whatever with respect to infringement of
               proprietary rights arising directly from the Qwest-Required
               Equipment except to the extent, if any, that KMC possesses the
               right to be indemnified by the vendor or manufacturer of the
               Qwest-Required Equipment from time to time for infringement of
               proprietary rights:

               i.   KMC or its suppliers will defend any claim, suit or
                    proceeding brought against Qwest insofar as it is based on a
                    claim that any Qwest-Required Equipment used hereunder
                    infringes a United States copyright or an existing United
                    States patent (issued as of August 31, 1999).  Qwest shall
                    notify KMC promptly in writing of the claim and give KMC and
                    its suppliers full authority, information, and assistance
                    for the defense.  If such claim has occurred, or in KMC's
                    opinion is likely to occur, Qwest agrees to permit KMC and
                    its suppliers, at KMC's option and expense, either to
                    procure for Qwest the right to continue using the Qwest-
                    Required Equipment or to replace or modify the same so that
                    it becomes noninfringing, or, if neither of the foregoing
                    alternatives is reasonably available, remove the Equipment
                    and refund Qwest the portion of the price for the MGS
                    Services reasonably attributable to such Equipment
                    depreciated or amortized by an equal annual amount over the
                    lifetime of the Qwest-Required Equipment as established by
                    Cisco or Nortel.

               ii.  KMC and its suppliers have no liability under this
                    Section 11 for any claim based upon the combination,
                    operation, or use of any Qwest-Required Equipment used
                    hereunder with equipment, devices, or software not supplied
                    by the vendor of such Qwest-Required Equipment.  KMC and its
                    suppliers have no liability for any claim under this Section
                    11 based upon alteration or modification by Qwest or a third
                    party of any Qwest-Required Equipment supplied hereunder.
                    Further, KMC and its suppliers

                                       11
<PAGE>

                    shall have no liability for any claim based upon compliance
                    with Qwest's designs, specifications, or instructions.

          b.   The following provisions relate to all Equipment other than
               Qwest-Required Equipment and all combinations of Equipment:

               i.   KMC agrees to defend and/or handle at its own expense, and
                    to indemnify and hold Qwest harmless from and against any
                    and all liabilities, losses, costs, damages and expenses
                    (including reasonable attorneys' fees attributable to such
                    claim) associated with, any claim or action against Qwest by
                    any third party based upon any actual or alleged
                    infringement or violation of a United States patent, or any
                    trademark, copyright, or trade secret of a third party
                    enforceable in the United States related to KMC's provision
                    of the MGS Services ("Infringement Claim"), provided that
                    Qwest shall approve the terms of any settlement or
                    compromise unless KMC demonstrates its financial capacity to
                    satisfy the settlement or compromise.

               ii.  KMC shall have the sole right to conduct the defense of
                    any such claim or action and all negotiations for its
                    settlement or compromise.  Qwest shall promptly notify KMC
                    of the subject claim and provide reasonable information in
                    connection with such claim.

               iii. KMC warrants that it has the full power and authority to
                    deliver, convey and grant to Qwest the related license and
                    other rights granted under this Agreement; and that KMC's
                    provision of MGS Services under this Agreement and Qwest's
                    use of the MGS Services related to the Equipment will not
                    constitute a misappropriation of any trade secrets or
                    constitute a patent, copyright or trademark infringement.

               iv.  This indemnity shall not extend to any claim of infringement
                    resulting from Qwest's unauthorized modification of
                    equipment of KMC or the combination of the Equipment or MGS
                    Services with services or equipment not provided by KMC or
                    by or for Qwest with KMC's express written approval.

     12.  General Indemnification and Limitation of Liability.

          a.  Each party shall indemnify the other party from any third-party
              claim or damages due to the injury or death of any individual, or
              the loss or damage to real or personal property, resulting from
              the willful or negligent acts, or omissions of the indemnifying
              party, its agents or employees.

                                       12
<PAGE>

          b.   NEITHER PARTY SHALL BE LIABLE TO THE OTHER OR TO ANY THIRD PARTY
               FOR ANY SPECIAL, INDIRECT, CONSEQUENTIAL, PUNITIVE OR EXEMPLARY
               DAMAGES, INCLUDING, BUT NOT LIMITED TO, LOST PROFITS, EVEN IF THE
               PARTIES HAVE KNOWLEDGE OF THE POSSIBILITY OF SUCH DAMAGES.  THE
               FOREGOING LIMITATION SHALL NOT APPLY IN THE EVENT OF: (i)  A
               CLAIM BROUGHT BY QWEST AGAINST KMC ARISING UNDER THE SECTION OF
               THIS AGREEMENT ENTITLED INFRINGEMENT (SECTION 11); (ii) EITHER
               PARTY'S BREACH OF THE CONFIDENTIALITY OBLIGATIONS OF SECTION 15
               (CONFIDENTIAL INFORMATION); OR (iii) THE  WILLFUL MISCONDUCT OF
               EITHER PARTY, ITS AGENTS, ITS EMPLOYEES OR NOMINEES ARISING OUT
               OF OR IN CONNECTION WITH THIS AGREEMENT.

          c.   IN NO EVENT SHALL A PARTY'S TOTAL LIABILITY TO THE OTHER UNDER
               THIS AGREEMENT EXCEED $5,000,000 (OTHER THAN QWEST'S PAYMENT OF
               THE MGS CIRCUIT RATES), EXCEPT WITH RESPECT TO THE GROSS
               NEGLIGENCE OR WILLFUL MISCONDUCT OF A PARTY.

          d.   In the event any applicable law does not allow the limitation or
               exclusion of liability as provided for in this Agreement, the
               subject limitation or exclusion of liability shall be deemed
               modified so as to limit or exclude the parties' liability for
               damages hereunder to the greatest extent permitted by such law.

     13.  Internet Disclaimers and Limitations.

          a.   Neither party will be liable or responsible for the Internet or
               any information contained thereon. Neither party will warrant,
               and neither will assume any responsibility for any consequences
               suffered by any person as a result of obtaining Internet access
               including without limitation, damages arising from accessing
               Internet content or from computer viruses.

          b.   KMC will have no responsibility for authentication of the end
               users accessing the MGS Circuits. Qwest will be responsible for
               controlling end user access to the MGS Circuits.

          c.   Qwest shall be responsible for billing its end users and all
               records related to such billing or accounting.

     14.  Force Majeure.  In no event shall either party be liable to the other
          party (other than for obligation to pay money) for any delay or
          failure to perform due to causes beyond the control and without the
          fault or negligence of the party claiming

                                       13
<PAGE>

          excusable delay, including but not limited to acts of God, fire,
          explosion, vandalism, cable cut, storm, governmental action, wars,
          strikes or other labor difficulties, supplier failures, breaches or
          delays (for the avoidance of doubt, to include any failure, breach or
          delay of Qwest as a supplier of KMC). Notwithstanding the foregoing,
          in the event of a force majeure (other than a supplier failure as to
          which Qwest is the supplier), KMC will use substantially the same or
          better efforts that it uses with respect to its other customers to
          restore the MGS Services for Qwest. If a force majeure condition
          continues for a period greater than [text deleted], either party
          may terminate only that MGS Service which is the subject of the force
          majeure condition without further penalty (except that Qwest shall not
          have the right to terminate any MGS Service pursuant to this Section
          14 as a result of a force majeur condition caused by Qwest).

     15.  Confidential Information.  Qwest and KMC agree that unless otherwise
          specifically provided in the applicable Exhibit and/or Schedule, the
          following confidentiality provisions shall apply.

          a.   All information (including the terms and conditions hereof)
               marked as confidential and disclosed by either party to the
               other, or which comes to the attention of either party or its
               employees, officers, directors, agents, investors and potential
               investors or advisors ("Representatives") during the course of
               work pursuant to the terms of this Agreement and any other
               information that a party receiving such information should know,
               by its nature, is confidential, shall be confidential
               information. Confidential information constitutes a valuable
               asset of and is proprietary to the party disclosing or originally
               possessing it.  KMC acknowledges that Qwest keeps its customers'
               records strictly confidential.  KMC and its Representatives shall
               keep strictly confidential any Qwest customer records, whether or
               not they are marked as confidential.  Neither party shall
               willfully disclose confidential information or knowingly permit
               its Representatives to disclose confidential information  to any
               person other than persons among its Representatives having a
               specific need to know in performance of the work or to any
               Financing Source as defined in Section 16 (b).  Each party shall
               take reasonable care to ensure fulfillment of this obligation,
               including instructing its Representatives and/or Financing
               Source(s) not to sell, lease, assign, transfer, use outside their
               scope of employment or reveal any confidential information or
               Qwest customer records without prior written consent of the other
               party.  KMC shall obtain the written agreement of its affiliates
               and Representatives who will receive Qwest customer records or
               other confidential information to conform to KMC's obligations
               under this Section.  KMC will not provide Qwest customer records
               or other confidential information provided by Qwest to the
               Financing Source(s) unless the Financing Source(s) provide
               written agreement to keep such information confidential.

                                       14
<PAGE>

          b.   If a subpoena or other legal process in any way concerning
               confidential information is served upon a party to which
               confidential information has been disclosed ("Recipient"), the
               Recipient shall notify the disclosing party ("Discloser")
               promptly, and the Recipient shall cooperate with the Discloser,
               at the latter's expense, in any lawful effort to contest the
               validity of such subpoena or other legal process.

          c.   This Section will in no way limit either party's ability to
               satisfy any governmentally required disclosure of its
               relationship with the other party, or either party's ability to
               satisfy any requests or demands generated in the course of audits
               of either party or either party's parent or either party's
               attorneys or auditors, provided such audits are conducted
               pursuant to non-disclosure obligations.

          d.   The obligations of confidentiality in this Section shall not
               apply to any information which a party has in its possession when
               disclosed to it by the other party, information which a party
               independently develops, information which is or becomes known to
               the public other than by breach of this Agreement or information
               rightfully received by a party from a third party without the
               obligation of confidentiality.

          e.   Each party acknowledges and agrees that in the event of a breach
               or threatened breach of the foregoing provisions, it will have no
               adequate remedy in money or damages and accordingly shall be
               entitled to injunctive relief; provided, however, that no
               specification of any legal or equitable remedy shall be construed
               as a waiver or prohibition against any other contractual, legal
               or equitable remedy available to either party hereunder;

          f.   Upon completion, expiration or termination of this Agreement, or
               at any other time upon request, each party shall return any and
               all related confidential information of the other party and all
               copies thereof (in whatever form and on whatever medium).

          g.   The terms of this section of the Agreement shall survive the
               expiration or termination of this Agreement.

     16.  Assignment; Rights of Subsidiaries.

          (a) Neither party may assign this Agreement without the prior written
          consent of the other party, which consent shall not be unreasonably
          withheld. If consent is not granted under this Section, the party
          seeking consent may terminate the Agreement upon sixty (60) days
          notice to the other party  or challenge the refusal to consent as
          unreasonable through appropriate legal action.  It shall not be
          unreasonable for KMC to withhold its consent if the assignee has a net
          worth less than that of Qwest as of the Effective Date.  The
          assignment or delegation of any

                                       15
<PAGE>

          of KMC's rights under this Agreement to any of the following shall be
          considered reasonable reasons for which Qwest may withhold its consent
          for such assignment: [text deleted], and/or [text deleted]. Any
                               --------------         --------------
          prohibited assignment or delegation shall be null and void.
          Notwithstanding the foregoing, either party may assign this Agreement
          to any company or entity controlling, controlled by or under common
          control with such party or its affiliates without the other party's
          consent; provided that the assignee has a net worth equal to or
          greater than that of Qwest or KMC, as may be applicable, as of the
          Effective Date. In addition, either party may assign this Agreement
          without the approval of the other party to any successor in interest
          resulting from a merger, acquisition, reorganization or transfer of
          all or substantially all of the assigning party's business with or to
          a successor; provided that the assignee has a net worth equal to or
          greater than that of Qwest or KMC, as may be applicable, as of the
          Effective Date.

          (b) Qwest acknowledges that in order for KMC to provide the services
          set forth in this Agreement KMC will finance the capital costs of this
          Agreement with  third party financing sources. KMC shall have the
          right to assign or collaterally assign this Agreement to a third party
          or parties providing financing for the capital expenses required to be
          undertaken by KMC in order to provide the services under this
          Agreement ("Financing Source(s)"), and Qwest shall execute and deliver
          consents to the assignment by KMC as are requested by the Financing
          Sources and are customary and usual, provided such consents contain
          non-disturbance rights of Qwest, and are otherwise reasonably
          acceptable to Qwest under these circumstances.

     17.  Modification; Amendment; Waiver. No modification, changes, amendment
          or supplement to this Agreement shall be binding upon the parties
          unless made in writing and duly signed by both parties.  The parties
          acknowledge that KMC shall finance the capital costs of this Agreement
          with Financing Sources.  Accordingly, Qwest agrees to cooperate with
          KMC to discuss and make such amendments or modifications to this
          Agreement as may be reasonably necessary or appropriate to finance and
          syndicate this Agreement to Financing Sources.  At no time shall any
          failure or delay by either party in enforcing any provisions,
          exercising any option, or requiring performance of any provisions, be
          construed to be a waiver, cancellation of same.  No effective waiver
          of any right hereunder shall be construed to be a waiver of any other
          right.

     18.  Notices.  All notices shall be in writing and either delivered
          personally or mailed, first class mail and postage prepaid, or by
          facsimile with electronically-generated confirmation of receipt that
          is followed with a mailed copy.  Notice shall be deemed communicated
          on receipt in case of personal delivery and five (5) days after
          mailing in the case of mailed notice (including the mailed copy of a
          facsimile transmission).  All such notices or other communications
          shall be addressed as set forth below, but either party may change its
          address by notice or other communication given in accordance with the
          provisions of this paragraph.

                                       16
<PAGE>

          If to Qwest:
          555 Seventeenth Street, Suite 1000
          Denver, Colorado 80202
          Attn:  President -- Internet and Multimedia Markets
          Attn:  General Counsel

          If to KMC:
          1545 Route 206
          Suite 300
          Bedminster, NJ  07921
          Attn:  General Counsel

     19.  Governing Law; Interpretation.  In all respects this Agreement shall
          be governed by the substantive laws of the State of New York without
          regard to conflict of law principles.

     20.  Dispute Resolution.

          a.   It is the intent of KMC and Qwest that any disputes which may
               arise between them or between the employees of each of them be
               resolved as quickly as possible.  Quick resolution may, in
               certain circumstances, involve immediate decisions made by the
               parties' representatives.  When such resolution is not possible,
               and depending upon the nature of the dispute, the parties hereto
               agree to resolve such disputes in accordance with the provisions
               of this paragraph; provided however, if they are unable to do so
               within sixty (60) days commencing with the date of the notice set
               forth in Section 20.b then either party may seek any and all
               remedies available at law or equity.

          b.   Qwest and KMC shall each designate, by separate letter,
               representatives as points of contact and decision-making for the
               pre-acceptance phases of the Agreement.  Any disputed issues
               arising under this Agreement shall be initially referred to the
               parties' designated representatives.  The parties' designated
               representatives shall render a mutually agreeable resolution of
               the disputed issue, in writing, within three (3) business days of
               such referral.  Either party may modify the designated
               representative upon written notice to the other party.

          c.   Any claims or disputes arising under the terms and provisions of
               this Agreement, or any claims or disputes which the parties'
               representatives are unable to resolve within the three (3) day
               time period shall continue to be resolved between the parties'
               representatives if mutually agreeable.

                                       17
<PAGE>

     21.  Attorney's Fees.  If a legal action or arbitration proceeding is
          commenced in connection with any dispute under this Agreement, the
          prevailing party shall be entitled to reasonable counsel fees,  costs
          and necessary disbursements incurred in connection with the action or
          proceeding, as determined by the court or arbitrators.

     22.  Inconsistencies. In the event of any inconsistency or conflict among
          this Agreement, or any Schedule or Exhibit, the governing provisions
          and interpretation necessary to resolve the inconsistency or conflict
          shall be based on the following order: the specific Schedule or
          Exhibit signed by the parties, followed next by the provisions of this
          Agreement.

     23.  Publicity. Neither party shall use the other party's name or logo or
          refer to such party directly or indirectly in any advertising, sales
          presentation to any other person, news release, release to any
          professional or trade publication or for any other purpose without
          such party's prior written approval, provided that either party may
          use the other party's name or logo, or both, in a list of such party's
          customers, if such use does not imply endorsement.  Either party shall
          be allowed to issue press releases and public announcements regarding
          this Agreement with the other party's prior written approval which
          shall not be unreasonably withheld.

     24.  Miscellaneous.

          a.   If any of the provisions of this Agreement are held invalid, the
               remaining provisions shall be unimpaired.

          b.   Headings are for reference only and shall not affect the meaning
               of any of the provisions of this Agreement.

          c.   The parties, who have both been represented by legal counsel,
               have jointly participated in negotiating and drafting this
               Agreement, including its Schedules, Exhibits and any attachments.
               In the event an ambiguity or question of intent or interpretation
               arises, this Agreement shall be construed as if jointly drafted
               by the parties and no presumption, inference or burden of proof
               shall arise favoring or disfavoring a party by virtue of
               authorship of any or all of the Agreement's provisions.

          d.   The rights and remedies set forth in this Agreement are not
               exclusive and are in addition to any other rights and remedies
               available in law or in equity.

          e.   The terms and provisions contained in this Agreement that by
               their sense and context are intended to survive shall survive the
               completion of performance and termination of this Agreement,
               including, without

                                       18
<PAGE>

               limitation, the obligation of making all payments due hereunder
               and to preserve the confidentiality of confidential information.

     25.  Relationship of the Parties.  The parties are independent contractors.
          Nothing in this Agreement or in the activities contemplated by the
          parties pursuant to this Agreement shall be deemed to create an
          agency, partnership, employment or joint venture relationship between
          the parties.  Each party shall be deemed to be acting solely on its
          own behalf and, except as expressly stated, has no authority to pledge
          the credit of, or incur obligations or perform any acts or make any
          statements on behalf of, the other party.  Neither party shall
          represent to any person or permit any person to act upon the belief
          that it has any such authority from the other party.  Neither party's
          officers or employees, agents or contractors shall be deemed officers,
          employees, agents or contractors of the other party for any purpose.

     26.  Compliance with Laws.

          a.  The parties shall comply with all applicable federal, state and
              local laws, regulations and ordinances as they relate to this
              Agreement and the MGS Services, including, but not limited to,
              the regulations of the United States Government, e.g., the
              provisions of Executive Order 11246 (as amended) of the President
              of the United States on Equal Employment Opportunity and the
              rules and regulations issued pursuant thereto.

          b.  KMC warrants, represents, covenants and agrees that it will not
              assign to perform any efforts under this Agreement any individual
              who is an unauthorized alien under the Immigration Reform and
              Control Act of 1986 or its implementing regulations.  KMC shall
              indemnify and hold harmless Qwest, its parent, subsidiaries and
              affiliated companies from and against any and all liabilities,
              damages, losses, claims or expenses (including attorneys' fees)
              arising out of any breach by KMC of this section.  In the event
              any KMC personnel or contractor working under this Agreement, or
              other individual(s) providing work to Qwest on behalf of KMC under
              this Agreement, are discovered to be unauthorized aliens, KMC will
              immediately remove such individuals from performing work and
              replace such individuals with individuals who are not unauthorized
              aliens. KMC shall indemnify and hold harmless Qwest, its parent,
              subsidiaries and affiliated companies from and against any and all
              liabilities, damages, losses, claims or expenses (including
              attorneys' fees) arising out of any breach by KMC of this section.

          c.  Neither party shall cause the other party to violate any ruling,
              order or determination by the Federal Communications Commission
              ("FCC") or any other governmental body relating to the provision
              of the MGS Services under the terms and conditions set forth in
              the Agreement.  Should such a

                                       19
<PAGE>

              ruling, order or determination become effective, the other party
              shall indemnify, defend and hold the other party harmless against
              any such event.

     27.  Successors.  This Agreement shall inure to the benefit of and be
          binding on the parties, and their heirs, successors, assigns and legal
          representatives, but nothing contained in this section shall be
          construed to permit an assignment or other transfer except as
          specifically provided herein.

     28.  Entire Agreement. This Agreement is comprised of this Agreement and
          any Schedule or Exhibits specified hereunder or which are added to
          hereto by the parties; such Schedule or Exhibits are incorporated by
          this reference and shall constitute a part of this Agreement as if
          fully set forth herein.  This Agreement constitutes the entire
          agreement between the parties and supersedes all previous agreements,
          promises, proposals, representations, understandings and negotiations,
          whether written or oral, between the parties respecting the subject
          matter hereof, except that this Agreement does not supersede the
          Original MGS Agreement to the extent, and only to the extent, that the
          terms and conditions of such Original MGS Agreement shall continue to
          apply to the Services ordered under such Original MGS Agreement prior
          to the Effective Date hereof.

     29.  Counterparts.  This Agreement may be executed in one or more
          counterparts, each of which shall constitute an original, but all such
          counterparts together shall constitute but one and the same
          instrument.

     IN WITNESS WHEREOF, the parties hereto have executed this Agreement as of
the date first written above.

 KMC Telecom VI Inc.

 By:  /s/ Roscoe C. Young
     -----------------------
 Name:
       ---------------------
 Title:
        --------------------

 Qwest Communications Corporation

 By:  /s/ Rick Weston
     -----------------------
 Name:    Rick Weston
       ---------------------
 Title:  SVP-QIS
        --------------------

                                       20
<PAGE>

                                   Schedule 1
                         Prices/Rates for MGS Services

Set forth on Appendix A to this Schedule is a table stating the MGS Circuit
Rates which will apply to the MGS Services. The prices are based on the number
of MGS Circuits installed and in operation, subject to the following rules :

1.   Rates. The rates for MGS Service for the term of this Agreement are set
     -----
     forth in Appendix A to this Schedule. The number of MGS Circuits for
     purposes of these prices shall include all MGS Circuits deemed installed
     pursuant to Section 3.b of the Agreement.

2.   If new or upgraded equipment is requested by Qwest prior to the expiration
     of the Agreement's term, Qwest will pay for such equipment.

3.   The parties agree and acknowledge that expenses and market prices related
     to the provision of the MGS Services may decrease in the future.  Should
     the market conditions change (including but not limited to the market
     prices for similar services), the parties agree to discuss in good faith
     reductions to the MGS Circuit Rates.  Qwest acknowledges that KMC may not
     agree to reduce the MGS Circuit Rates without first obtaining the consent
     of a Financing Party and KMC has no obligation hereunder to obtain such
     consent.

4.   As set forth in Section 7 of the Agreement, the MGS Circuits provided
     pursuant to the Implementation Schedule under this Agreement shall have an
     initial term which is co-terminous with the initial term of the Agreement
     (and shall terminate when this Agreement is terminated), and each
     additional MGS Circuit shall have an initial term commencing on the date it
     is installed and ending forty-two (42) months thereafter. The MGS Circuit
     Rates set forth in this Schedule shall apply to each MGS Circuit during the
     initial term for such MGS Circuit.  Unless the Agreement has been earlier
     terminated, substituted for another agreement where such agreement
     specifically amends this Agreement, or is not renewed by the parties,
     following the expiration of the initial term of the Agreement, the parties
     agree to enter into good faith negotiations with regard to rates, terms and
     conditions which will apply to MGS Circuits ordered under this Agreement
     (not including any MGS Circuits which may be expressly ordered separately
     under later agreements between the parties) after the expiration of the
     initial term for each MGS Circuit, provided that the MGS Circuit Rates set
     forth herein (as they exist as of that date) shall continue to apply during
     such negotiations.

                                       21
<PAGE>

                            Appendix A to Schedule 1

1.   Monthly charge of $[text deleted] per [text deleted].
                        --------------     --------------

2.   Location Adjustment.  Qwest acknowledges that, because of the
     characteristics of the locations at which Qwest has ordered or may order
     MGS Service hereunder, KMC may be required to incur higher than normal
     [text deleted], [text deleted] or [text deleted] costs with respect to one
     --------------  --------------    --------------
     or more MGS Circuits provided hereunder.  In the event that, following
     review and consent by Qwest as described below, KMC incurs [text deleted],
                                                                --------------
     [text deleted] or [text deleted] costs in excess of [text deleted] with
     --------------    --------------                    --------------
     regard to one or more MGS Circuits, then as to each such Circuit, in
     addition to the monthly charge set forth in paragraph 1, above, Qwest shall
     pay a monthly surcharge equal to the amount by which the cost incurred by
     KMC of [text deleted], [text deleted] or [text deleted] attributable to
            --------------  --------------    --------------
     such MGS Circuit exceeds [text deleted].  KMC shall notify Qwest in advance
                              --------------
     of any location at which such surcharge will be applicable and Qwest will
     either consent to such surcharge (such consent not to be unreasonably
     withheld) or cooperate with KMC in identifying an alternative location at
     which MGS Service will be provided, in which case such alternative location
     shall be subject to the surcharge (if applicable).  In the event KMC incurs
     [text deleted], [text deleted] or [text deleted] costs of less than [text
     --------------  --------------    --------------                    -----
     deleted] with regard to one or more MGS Circuits, then as to each such
     --------
     Circuit, KMC shall provide to Qwest a credit equal to the amount by which
     the cost incurred by KMC for [text deleted], [text deleted] or [text
                                  --------------  --------------    -----
     deleted] attributable to such MGS Circuit is less than [text deleted].
     --------                                               --------------

3.   Maintenance Costs.  KMC shall provide up to twenty-four (24) hours of on-
     site maintenance (not including travel time) per location per calendar
     month.  In the event the hours of such on-site maintenance at any location
     exceed twenty-four (24) in any calendar month, Qwest will reimburse KMC for
     its reasonable costs of providing the hours of on-site maintenance in
     excess of twenty-four (24).  KMC will notify Qwest when it has attained
     this twenty-four (24) hour threshold at a given location.  To the extent
     Qwest fails to remotely monitor the equipment or software at any site or
     fails to notify KMC of any deficiency which Qwest remotely detects, KMC
     shall bear no responsibility for a failure of the subject equipment or
     software under this Agreement or otherwise to the extent that such failure
     could have been prevented or resolved with notice from Qwest regarding such
     deficiency as required hereunder.

4.   Trunk Provisioning.  If Qwest desires that KMC provision two-way trunks in
     connection with one or more of the MGS Services, Qwest shall submit a
     written request to KMC and KMC shall, within 15 days, provide Qwest with a
     written estimate of all direct costs, charges and fees payable by KMC to
     third parties in connection with the provisioning, maintenance and
     operation of such two-way trunks (to the extent they exceed costs
     associated with one-way trunks) and an estimated time frame in which KMC
     will order the same.  If Qwest accepts such estimates of charges and the
     time frame for ordering, Qwest shall provide KMC with a written acceptance
     and KMC shall order such two-way trunks

                                       22
<PAGE>

     within such time-frame and thereafter Qwest shall be responsible for paying
     for all direct costs, charges and fees payable by KMC in connection with
     the provisioning, maintenance and operation of the two-way trunks to the
     extent they exceed costs associated with one-way trunks.

                                       23
<PAGE>

                                   Schedule 2
                                 Service Levels

     1.      Service Level.   For purposes of this Agreement, "Service Level" or
             --------------
"Service Levels" means the level of service at or above which KMC shall provide
the MGS Services to Qwest and includes the following elements (all of which
shall be based on industry-standard measurements) provided by KMC:

     (i)     24x7 (at the KMC POP) remote hands services;

     (ii)    P.01 grade of service measured on a calendar month basis, for the
             portion of the KMC network, from and including KMC switches (but
             not including Qwest-Required Equipment), to the DNAC, during peak
             busy hours;

     (iii)   a time to repair of four (4) hours from the time Qwest's calls to
             the KMC help desk are answered, for each port, MGS Circuit, or MGS
             Server;

     (iv)    meeting or exceeding industry standards for onsite power and
             environmental control and quality provided to devices; local
             interconnection trunks, local loop access, and for out-of-band
             access circuits to the devices under this Agreement; and

     (v)     an average uptime of 99.99% for the portion of the KMC network,
             from and including KMC switches (but not including Qwest-Required
             Equipment), to the DNAC, measured on a per-MGS Circuit basis.

2.   Failure.  KMC will be deemed to have failed to meet the Service Levels
     -------
above if:

     (i)     at any time KMC fails to satisfy its obligations set forth in
             subsections 1(i) and/or 1(iv) of this Schedule 2; and/or

     (ii)    in any two calendar months within any six (6) consecutive calendar
             month period of the Agreement, ten percent (10%) of the MGS
             Circuits provided under this Agreement fail to meet any of the
             standards set forth in subsections 1(ii), 1(iii) and/or 1(v) of
             this Schedule 2; provided that, within ten (10) business days after
             the end of any calendar month in which such failure of MGS Circuits
             to meet such standards has occurred, Qwest shall give KMC written
             notice of such failure and provide to KMC all information within
             Qwest's possession that is reasonably calculated to assist KMC in
             taking steps to prevent the recurrence of such failure.

                                       24<PAGE>

                                                                   Exhibit 10.21

               CERTAIN PORTIONS OF THIS EXHIBIT HAVE BEEN OMITTED
                 BASED ON A REQUEST FOR CONFIDENTIAL TREATMENT

                  OMITTED PORTIONS HAVE BEEN SEPARATELY FILED
                  WITH THE SECURITIES AND EXCHANGE COMMISSION

                                                                  Execution Copy

                                AMENDMENT NO. 1
                                       TO
                      MEDIA GATEWAY SERVICES AGREEMENT III

          THIS AMENDMENT NO 1. TO MEDIA GATEWAY SERVICES AGREEMENT III
("Amendment") dated as of August 31, 2000, by and between Qwest Communications
  ---------
Corporation, a Delaware corporation ("Qwest") and KMC Telecom VI Inc., a
                                      -----
Delaware corporation ("KMC").
                       ---

          WHEREAS, Qwest and KMC are parties to that certain Media Gateway
Services Agreement III dated as of June 30, 2000 (the "MGS Agreement") pursuant
                                                       -------------
to which, among other things, KMC has agreed to provide to Qwest, and Qwest has
agreed to compensate KMC for, certain services; and

          WHEREAS, the parties have agreed to amend the MGS Agreement on the
following terms;

          NOW, THEREFORE, in consideration of the premises set forth above, and
for other good and valuable consideration, the receipt and sufficiency of which
are hereby acknowledged, KMC and Qwest agree as follows:

      1.  Definitions.  Capitalized terms not otherwise defined herein shall
          -----------
have the meanings ascribed to them in the MGS Agreement.

      2.  Amendment to the MGS Agreement.  Effective as of the date first above
          ------------------------------
written and subject to the execution of this Amendment by the parties hereto,
the MGS Agreement shall be and hereby is amended as follows:

          (a)  Section 3.a is hereby amended by deleting the second sentence
               -----------
     thereof and substituting the following therefor:

     "Charges for the MGS Circuits will be as follows: (a) on [text deleted]
                                                              --------------
     Qwest shall commence payment on a monthly basis for the [text deleted] of
                                                             --------------
     (x) [text deleted] of all MGS Circuits deemed installed (as described
         --------------
     below) as of [text deleted] or (y) the [text deleted] of MGS Circuits in
                  --------------            --------------
     service as of November 1, 2000 plus all out of pocket and third party costs
     incurred by KMC and payable by Qwest pursuant to Appendix A to Schedule 1
     for [text deleted] of all MGS Circuits deemed installed ("Out of Pocket
         --------------
     Costs") as of [text deleted]; (b) on
                   --------------

                                       1
<PAGE>

     [text deleted] Qwest shall make, as the monthly payment for the month of
     --------------
     [text deleted], a payment in the amount of the [text deleted] of (x) [text
     --------------                                 --------------        -----
     deleted] of all MGS Circuits deemed installed as of [text deleted] or (y)
     --------                                            --------------
     the [text deleted] of MGS Circuits in service as of [text deleted] plus
         --------------                                  --------------
     [text deleted] of all Out of Pocket Costs as of [text deleted] not
     --------------                                  --------------
     previously paid by Qwest; and Qwest shall also commence monthly payments
     for the [text deleted] of (x) [text deleted] of all MGS Circuits deemed
             --------------        --------------
     installed as of [text deleted] or (y) the [text deleted] of MGS Circuits in
                     --------------            --------------
     service as of [text deleted] plus [text deleted] of all Out of Pocket Costs
                   --------------      --------------
     as of [text deleted] not previously paid by Qwest; (c) on March 1, 2001
           --------------
     Qwest shall commence monthly payments for the [text deleted] of (x) [text
                                                   --------------        -----
     deleted] of all MGS Circuits deemed installed or (y) the [text deleted] of
     --------                                                 --------------
     MGS circuits in service plus [text deleted] of all Out of Pocket Costs not
                                  --------------
     previously paid by Qwest, and (d) on [text deleted] Qwest shall commence
                                          --------------
     payment for all MGS Circuits deemed installed."

        3.   Representations and Warranties of Qwest and KMC. Qwest and KMC
             -----------------------------------------------
hereby represent and warrant as follows:

             (a)  This Amendment and the MGS Agreement, as amended hereby,
     constitute legal, valid and binding obligations of Qwest and KMC and are
     enforceable against Qwest and KMC in accordance with their terms.

             (b)  Upon the effectiveness of this Amendment, Qwest and KMC hereby
     reaffirm all representations and warranties made in the MGS Agreement, and
     to the extent the same are not amended hereby, agree that all such
     representations and warranties shall be deemed to have been remade as of
     the date of delivery of this Amendment, unless and to the extent that any
     such representation and warranty is stated to relate solely to an earlier
     date, in which case such representation and warranty shall be true and
     correct as of such earlier date.

             (c)  As of the date hereof, and after giving effect to this
     Amendment, each of Qwest and KMC shall be in compliance with all the terms
     and provisions set forth in the MGS Agreement, as amended hereby, on its
     part to be observed or performed, and no Event of Default shall have
     occurred and/or be continuing.

        4.   Reference to and Effect on the MGS Agreement.
             --------------------------------------------

             (a)  The MGS Agreement, as amended hereby, and all other documents,
     instruments and agreements executed and/or delivered in connection
     therewith, remains in full force and effect, and are hereby ratified and
     confirmed.

             (b)  Except as expressly provided herein, the execution, delivery
     and effectiveness of this Amendment shall not operate as a waiver of any
     right, power or remedy of Qwest or KMC, nor constitute a waiver of any
     provision of the MGS Agreement or any other documents, instruments and
     agreements executed and/or delivered in connection therewith.

                                       2
<PAGE>

     5.  GOVERNING LAW.  THIS AMENDMENT SHALL BE GOVERNED BY AND CONSTRUED IN
         -------------
ACCORDANCE WITH THE OTHER REMAINING TERMS OF THE MGS AGREEMENT AND THE INTERNAL
LAWS (AS OPPOSED TO CONFLICT OF LAW PROVISIONS) OF THE STATE OF NEW YORK.

     6.  Paragraph Headings.  The paragraph headings contained in this
         ------------------
Amendment are and shall be without substance, meaning or content of any kind
whatsoever and are not a part of the agreement among the parties hereto.

     7.  Counterparts.  This Amendment may be executed in one or more
         ------------
counterparts, each of which shall be deemed an original, but all of which
together shall constitute one and the same instrument.

                                       3
<PAGE>

          IN WITNESS WHEREOF, this Amendment has been duly executed as of the
day and year first above written.

 KMC Telecom VI Inc.

 By: /s/ William H. Stewart
     --------------------------
 Name:   William H. Stewart
       ------------------------
 Title:  Chief Financial Officer
        ------------------------

 Qwest Communications Corporation

 By: /s/ Rick Weston
     --------------------------
 Name:   Rick Weston
       ------------------------
 Title:  SVP-QIS
        -----------------------

                                       4

Source: [{"source": "alea-institute/alea-institute/kl3m-data-edgar-agreements/train-00015-of-00352.parquet"}, [{"source": "alea-institute/alea-institute/kl3m-data-edgar-agreements/train-00015-of-00352.parquet"}]]