<PAGE>

                                                                   EXHIBIT 10.12

[*]=CERTAIN CONFIDENTIAL INFORMATION CONTAINED IN THIS DOCUMENT, MARKED BY
BRACKETED ASTERISKS HAS BEEN OMITTED AND FILED SEPERATELY WITH THE SECURITIES
AND EXCHANGE COMMISSION PURSUANT TO RULE 406 OF THE SECURITIES ACT OF 1933, AS
AMENDED.


Embratel                                       Amendment Number VES-8-IDN-1-1999
--------------------------------------------------------------------------------

        AMENDMENT TO MASTER AGREEMENT FOR VALUE ADDED SERVICES (BRAZIL)
                                BY AND BETWEEN
  AOL BRASIL LTDA. AND EMPRESA BRASILEIRA DE TELECOMUNICACOES S.A. - EMBRATEL

     This Amendment (the "Amendment"), effective as of May 10, 2000 (the
"Amendment Date"), is entered into by and between AOL BRASIL LTDA., a Brazilian
corporation headquartered at Avenida Industrial 600, 2o. Andar, Santo Andre,
08090-500, Sao Paulo - SP, registered with the Ministerio de Fazenda under
number 03.032.579/0001-62, represented by its President, Manoel L. Amorim,
hereinafter called AOL, and EMPRESA BRASILEIRA DE TELECOMUNICACOES S.A. -
EMBRATEL, a Brazilian corporation headquartered at Av. Presidente Vargas, 1012,
CEP 20179-900, Rio de Janeiro - RJ, registered with the Ministerio de Fazenda
under number 33.530.486/0001-29, represented by its Services Director, Eduardo
Levy Cardoso Moreira, and its Regional Director, Luiz Claudio Andrade Cyriaco,
hereinafter called EMBRATEL, and modifies, and is incorporated into, the Master
Agreement for Value Added Services (Brazil) dated October 18, 1999 by and
between AOL and EMBRATEL (the "Agreement"). This Amendment modifies the sections
of the Agreement as indicated below. Unless modified herein, all other terms
defined in the Agreement shall have the same meaning when used in this
Amendment. All terms and conditions of the Agreement not otherwise specifically
modified in this Amendment remain unchanged and in full force and effect. In the
case of conflict between the terms of this Amendment and the remaining terms and
conditions of the Agreement, the terms of this Amendment shall control.

1.   INTERNATIONAL TRANSIT SERVICES

Section 1 of the Agreement is hereby amended by adding the following provisions
at the end of Section 1:

          The services under this Agreement include the provision
          of fully-redundant dedicated private line backhaul
          capacity to AOL between Brazil and the United States
          ("International Transit Services").

          EMBRATEL shall provide International Transit Services
          to AOL as follows:

          (a)  Within ten (10) days of the Amendment Date,
               EMBRATEL shall re-route AOL's existing traffic
               over [*] of Internet bandwidth capacity on the [*]
               submarine cable (the "Initial [*] Capacity").

          (b)  EMBRATEL shall provide AOL a dedicated leased line
               fiber-optic circuit with up to STM-1 bandwidth
               capacity on the Americas II submarine cable (the
               "Americas II Circuit") between Brazil and the USA.
               EMBRATEL shall provide AOL the capacity not later
               than July 1, 2000. EMBRATEL shall provide AOL the
               Americas II Circuit for ten (10) years starting on
               the date AOL activates any capacity on the
               Americas II Circuit. EMBRATEL shall notify AOL in
               writing of the date in which the Americas II
               Circuit will be made available to AOL at least
               fifteen (15) days prior such date.

          (c)  AOL may choose to: (i) activate the entire STM-1
               bandwidth capacity on the Americas II Circuit upon
               the earlier of July 1, 2000 or the date the
               Americas II Circuit is made available to AOL; or
               (ii) initially activate DS-3 bandwidth capacity on
               the Americas II Circuit upon the earlier of July
               1, 2000 or the date the Americas II Circuit is
               made available to AOL, and, thereafter, activate
               additional units of DS-3 bandwidth capacity until
               the entire STM-1 capacity on the Americas II
               Circuit is filled. Such activation will be made by
               AOL by providing 30 days prior written notice to

                                       1
                             HIGHLY CONFIDENTIAL
<PAGE>

Embratel                                       Amendment Number VES-8-IDN-1-1999
--------------------------------------------------------------------------------

               EMBRATEL specifying the bandwidth to be activated.

          (d)  When the entire STM-1 has been activated, Embratel
               will, at AOL's request, make its best efforts to
               combine the three DS3s into a single OC3c
               (concatenated) on the STM-1.

          (e)  Upon activation of Americas II capacity for
               EMBRATEL's Internet backbone, EMBRATEL shall route
               all AOL traffic over the Americas II Circuit
               (including traffic previously routed over the
               Initial [*] Capacity and the Additional [*]
               Capacity (as defined in Section 1(f), if
               applicable). Embratel shall move AOL's traffic to
               Americas II Internet before any other customer.

          (f)  If EMBRATEL does not provide the Americas II
               dedicated Circuit to AOL by July 1, 2000 as
               provided in Section 1(b), EMBRATEL shall provide
               AOL, in addition to the Initial [*] Capacity, [*]
               of bandwidth capacity on the [*] submarine cable
               (the "Additional [*] Capacity") as of July 1, 2000
               and re-route existing AOL traffic not already
               routed through the Initial [*] Capacity over the
               Additional [*] Capacity. In any event, EMBRATEL
               shall use its best commercial efforts to provide
               AOL the Additional [*] Capacity as of April 30,
               2000 and re-route existing AOL traffic not already
               routed through the Initial [*] Capacity over the
               Additional [*] Capacity.

          (g)  If EMBRATEL does not provide AOL the leased line
               over Americas II Circuit by [*], AOL may (i)
               terminate the provision of the Americas II Circuit
               [*], or (ii) terminate the provision of all
               International Transit Services [*], including,
               without limitation, the termination penalty of
               Section 1(h), by providing EMBRATEL written notice
               of such termination.

          (h)  AOL may terminate the provision of International
               Transit Services at any time upon the delivery of
               a 30-day notice and the payment of an early
               termination fee consisting of [*] of the monthly
               International Transit Fees multiplied by the
               number of months remaining in the term of the
               Agreement.

          (i)  International Transit Services shall be provided
               by EMBRATEL in accordance with the performance
               measures set forth in Schedule A hereto
               ("Performance Measures").

          (j)  If EMBRATEL fails to meet Performance Measures and
               such failure results in an outage of International
               Transit Services, EMBRATEL shall credit AOL, in
               the invoice for the month immediately following
               the month in which the outage occurs, an amount
               equal to [*] (as defined below) [*], multiplied by
               a fraction, the numerator of which equals the
               number of hours of the outage, and the denominator
               of which equals the number of hours in the month
               in which the outage occurred (e.g., 720). EMBRATEL
               shall not be required to make such credit if the
               outage results from:

                    (1)  non-routine operations undertaken by a
                         Party, provided the Parties have agreed
                         in writing in advance of such operations
                         to excuse outages resulting from such
                         operations;

                                       2
                              HIGHLY CONFIDENTIAL
<PAGE>

Embratel                                       Amendment Number VES-8-IDN-1-1999
--------------------------------------------------------------------------------

                    (2)  an Act of God;

                    (3)  a force majeure event; or

                    (4)  reasonable scheduled maintenance
                         performed by EMBRATEL, provided EMBRATEL
                         has provided AOL at least fifteen (15)
                         days prior written notice of such outage
                         and the reasons therefor;

2.   [*]

Section 2.5 of the Agreement is hereby replaced in its entirety by the following
provisions:

          2.5  [*]. EMBRATEL shall provide AOL [*] under this
               Agreement [*]

3.   INTERNATIONAL TRANSIT FEES

Section 2.1(d) of the Agreement is hereby amended by deleting clauses (c)
("routing through Internet international circuits") and (d) ("recurring backhaul
circuit charges"). A new Section 2.6 is hereby incorporated to the Agreement
consisting of the following provisions:

          2.6  International Transit Fees. Fees for International
               --------------------------
          Transit Services ("International Transit Fees") are, as
          of the date AOL activates bandwidth in the Americas II
          Circuit, the following, subject to item 2.1 (f) of the
          Agreement:

          (a)  US$[*] per month for the first unit of DS-3
               capacity activated if AOL activates an initial DS-
               3 capacity on the Americas II Circuit as provided
               in Section 1(c)(ii).

          (b)  US$[*] per month for the second unit of DS-3
               capacity activated if AOL activates an initial DS-
               3 capacity on the Americas II Circuit as provided
               in Section 1(c)(ii) and subsequently activates a
               second unit of DS-3 capacity. This price is
               available only if this second DS3 terminates at
               the same location as the first DS3 above.

          (c)  US$[*] per month if AOL activates the entire STM-1
               capacity on the Americas II Circuit either (i) as
               provided in Section 1(c)(i), or (ii) if AOL
               initially activates DS-3 capacity on the Americas
               II Circuit pursuant to Section 1(b)(ii) and
               subsequently activates the second and third units
               of DS-3 capacity (e.g., all three units of DS-3
               capacity are activated).

          The prices presented above do not include any taxes.

          The International Transit Fees are for an international
          circuit from AOL in Virginia - USA, terminating in one
          of EMBRATEL's operations buildings in Sao Paulo -
          Brazil. Any changes to the circuit termination outside
          of EMBRATEL's facilities in the city of Sao Paulo may
          require price adjustment.

          In case AOL does not activate: (i) the second DS-3
          capacity within [*] of the the date AOL first activates
          capacity on the Americas II Circuit, then, at such
          time, EMBRATEL shall charge AOL for the second DS-3,
          according to Section 2.6(b), as if such capacity was
          activated; (ii)

                                       3
                              HIGHLY CONFIDENTIAL
<PAGE>

Embratel                                       Amendment Number VES-8-IDN-1-1999
--------------------------------------------------------------------------------

          the entire STM-1 capacity within 36 (thirty-six) months
          of the date AOL first activates capacity on the
          Americas II Circuit, then, at such time, EMBRATEL shall
          charge AOL for the entire STM-1 capacity, according to
          Section 2.6 (c), as if such capacity was activated. As
          of the date AOL activates any bandwidth in the Americas
          II Circuit, the Base Price shall not include fees for
          International Transit Services.

4.   MODEM FEES

Section 2.1(a) is hereby amended by replacing the Base Price of [*] per [*]
Modem per month with a new Base Price of [*] per [*] Modem per month, which does
not include fees for International Transit Services. The new Base Price set
forth above shall become effective as of the date AOL activates bandwidth on the
Americas II circuit or as of the date AOL terminates the provision of
International Transit Services.

5.   MARKET PRICING

A new Section 2.7 is hereby incorporated to the Agreement consisting of the
following provisions:

          2.7  Market Pricing.
               --------------

          (a)  If AOL receives [*] with the capability to provide
               telecommunications services in Brazil similar to
               the International Transit Services to AOL [*]
               EMBRATEL to AOL for International Transit
               Services, then, no more often than once a year,
               upon presentation of such [*], EMBRATEL shall
               enter into good faith discussions with AOL in
               order to adjust the International Transit Fees in
               this Agreement to the market conditions, through
               price and/or term adjustments.

6.   MARKET PRICING REMEDIES

A new Section 2.8 is hereby incorporated to the Agreement consisting of the
following provisions:

          2.8  Market Pricing Remedies.
               -----------------------

          (a)  If the parties are unable to reach an agreement
               regarding the International Transit Fees as
               provided in Section 2.7(a), then AOL may,
               terminate the provision of International Transit
               Services without incurring any liability to
               EMBRATEL, including, without limitation, the
               termination penalty of Section 1(h), by providing
               written notice to EMBRATEL of such termination.

7.   PAYMENT TERMS

Section 2.4 of the Agreement is hereby amended by adding the following
provisions at the beginning of such section:

               EMBRATEL will invoice AOL International Transit
               Fees for payment in Brazilian Reais, on a monthly
               basis in arrears. The prices presented in Section
               2.6 are in US Dollars and shall be converted to
               Brazilian Reais every month, one day prior to the
               release of the corresponding invoice, through the
               PTAX800 closing exchange rate for selling of the
               US Dollar, published by Banco Central do Brasil -
               SISBACEN.

                                       4
                              HIGHLY CONFIDENTIAL
<PAGE>

Embratel                                       Amendment Number VES-8-IDN-1-1999
--------------------------------------------------------------------------------

8.   TERM

Section 8.1 of the Agreement is hereby amended by deleting the first sentence of
such section ("The term of this relationship shall be three (3) years from the
Effective Date") and replacing it with the following provisions:

               The term of the Agreement shall be ten (10) years
               from the date AOL activates any capacity on the
               Americas II Circuit, provided that the provision
               of Modems and services related thereto (other than
               International Transit Services) shall terminate
               three (3) years after the Effective Date of the
               Agreement.

9.   FORCE MAJEURE

Section 14.3(d) of the Agreement is hereby amended by adding the following
provisions to the end of the first sentence of such section:

               (iii) terminate the provision of International
               Transit Services if International Transit
               Services are materially affected by such force
               majeure circumstances.

10.  LANGUAGE AND COUNTERPARTS

This Amendment is executed in English, and AOL shall, within thirty (30) days as
of the Amendment Date, provide EMBRATEL a translation of this Amendment into
Portuguese to be executed by both Parties. The Parties shall agree upon the
final version of the Portuguese translation as soon as practicable. In case of
any discrepancies between the English version and the Portuguese version of this
Amendment, the Portuguese version shall prevail. This Amendment may be executed
in several counterparts , each of which shall be deemed an original, but all of
which, when taken together, shall constitute one and the same instrument.

11.  CERTAIN CONDITIONS

     Section 10.5 of the Agreement is hereby replaced in its entirety by the
     following provisions: EMBRATEL shall designate 5% of invoiced amounts less
     taxes due to the domestic portion (Dedicated and Shared Modems) of this
     Agreement to joint marketing.

                                       5
                              HIGHLY CONFIDENTIAL
<PAGE>

Embratel                                       Amendment Number VES-8-IDN-1-1999
--------------------------------------------------------------------------------

12.  DEPLOYMENT PLAN

     Exhibit C of the Agreement is hereby amended by replacing the "Deployment
Plan" table by the following provisions:

            -------------------------------------------------------
                    AOL Designated City               Total
            -------------------------------------------------------
            Americana                                   30
            -------------------------------------------------------
            Anapolis                                    60
            -------------------------------------------------------
            Aracaju                                     60
            -------------------------------------------------------
            Aracatuba                                   30
            -------------------------------------------------------
            Araraquara                                  90
            -------------------------------------------------------
            Barueri                                     90
            -------------------------------------------------------
            Bauru                                       90
            -------------------------------------------------------
            Belem                                      120
            -------------------------------------------------------
            Belo Horizonte                             600
            -------------------------------------------------------
            Blumenau                                    60
            -------------------------------------------------------
            Boa Vista                                   30
            -------------------------------------------------------
            Brasilia                                   420
            -------------------------------------------------------
            Campinas                                   480
            -------------------------------------------------------
            Campo Grande                               120
            -------------------------------------------------------
            Campos                                      60
            -------------------------------------------------------
            Cascavel                                    60
            -------------------------------------------------------
            Catanduva                                   30
            -------------------------------------------------------
            Caxias do Sul                               90
            -------------------------------------------------------
            Chapeco                                     30
            -------------------------------------------------------
            Criciuma                                    30
            -------------------------------------------------------
            Cuiaba                                      90
            -------------------------------------------------------
            Curitiba                                   600
            -------------------------------------------------------
            Florianopolis                              180
            -------------------------------------------------------
            Fortaleza                                  240
            -------------------------------------------------------
            Goiania                                    180
            -------------------------------------------------------
            Governador Valadares                        30
            -------------------------------------------------------
            Joao Pessoa                                 90
            -------------------------------------------------------
            Joinville                                  120
            -------------------------------------------------------
            Juiz de Fora                                90
            -------------------------------------------------------
            Jundiai                                    120
            -------------------------------------------------------
            Londrina                                   150
            -------------------------------------------------------
            Macapa                                      30
            -------------------------------------------------------
            Maceio                                      90
            -------------------------------------------------------
            Manaus                                     180
            -------------------------------------------------------
            Marilia                                     60
            -------------------------------------------------------
            Maringa                                     90
            -------------------------------------------------------
            Natal                                       90
            -------------------------------------------------------
            Osasco                                     240
            -------------------------------------------------------
            Palmas                                      30
            -------------------------------------------------------
            Pelotas                                     60
            -------------------------------------------------------
            Piracicaba                                  90
            -------------------------------------------------------
            Ponta Grossa                                60
            -------------------------------------------------------
            Porto Alegre                               540
            -------------------------------------------------------
            Porto Velho                                 30
            -------------------------------------------------------
            Presidente Prudente                         90
            -------------------------------------------------------
            Recife                                     180
            -------------------------------------------------------
            Ribeirao Preto                             240
            -------------------------------------------------------
            Rio Branco                                  30
            -------------------------------------------------------

                                       6
                              HIGHLY CONFIDENTIAL
<PAGE>

Embratel                                       Amendment Number VES-8-IDN-1-1999
--------------------------------------------------------------------------------

            -------------------------------------------------------
            Rio de Janeiro                             960
            -------------------------------------------------------
            Salvador                                   360
            -------------------------------------------------------
            Santa Maria                                 60
            -------------------------------------------------------
            Santo Andre                                240
            -------------------------------------------------------
            Santos                                     240
            -------------------------------------------------------
            Sao Bernardo do Campo                      240
            -------------------------------------------------------
            Sao Carlos                                  30
            -------------------------------------------------------
            Sao Jose do Rio Preto                      120
            -------------------------------------------------------
            Sao Jose dos Campos                        240
            -------------------------------------------------------
            Sao Luis                                    90
            -------------------------------------------------------
            Sao Paulo                                1.560
            -------------------------------------------------------
            Sorocaba                                    50
            -------------------------------------------------------
            Teresina                                    60
            -------------------------------------------------------
            Uberaba                                     30
            -------------------------------------------------------
            Uberlandia                                 210
            -------------------------------------------------------
            Varginha                                    30
            -------------------------------------------------------
            Vitoria                                     60
            -------------------------------------------------------
                           TOTAL                    11.280
            -------------------------------------------------------

IN WITNESS WHEREOF, the parties hereto have executed this Amendment effective as
of the Amendment Date.

Sao Paulo, May 10, 2000

AOL BRASIL LTDA.                            EMPRESA BRASILEIRA DE
                                            TELECOMUNICAcoES S.A.- embratel

By: /s/ Luiz Claudio A. Cyriaco             By: /s/ Manoel L. Amorim
-------------------------------------       ------------------------------------
Name:  Luiz Claudio A. Cyriaco              Name:  Manoel L. Amorim
Regional Director                           President

By: /s/ Edson Pinheiro Alves
-------------------------------------
Name:  Edson Pinheiro Alves
Sales Supervisor

WITNESSES:

By: /s/ Luciana Barreto                     By: ________________________________
   ------------------------------------
Luciana C. Zanata Mello Barreto
RG 20.612.932

                                       7
                              HIGHLY CONFIDENTIAL
<PAGE>

Embratel                                       Amendment Number VES-8-IDN-1-1999
--------------------------------------------------------------------------------

                                  SCHEDULE A
                             PERFORMANCE MEASURES

 .    International Transit Services shall be provided on a net availability of
     99.9% (measured over the preceding 12 month period).

 .    The undersea portion of the International Transit Services meets the
     performance criteria of ITU-T G.826 and has line monitoring and collapse
     ring. Support for protection switching will made available to AOL as soon
     as it becomes available to any other customers.

 .    The inland portion of the International Transit Services has the ability to
     carry commercial traffic between the system interface at the Fortaleza
     cable station to the inland point of interface meeting performance criteria
     of ITU-T G.826 and has collapse ring capability. Support for protection
     switching will made available to AOL as soon as it becomes available to any
     other customers. The interface to the system shall be an electrical
     interface as specified in ITU Recommendation G.957 and be 1+1 (or
     equivalent) protected.

 .    The connection between the Fortaleza cable station and Sao Paulo will be
     delivered through EMBRATEL's fiber-optic fully redundant.

 .    Day to day operation of the International Transit Services will be under
     the control of the Embratel Network Operations Center (the "Embratel NOC").
     The Embratel NOC will be manned 24 hours per day, 7 days per week, and will
     provide comprehensive end to end monitoring of the system between AOL -
     Virginia, Fortaleza Cable Station, and Sao Paulo.

 .    The Embratel NOC will act as the Restoration Control Office (RCO) and
     coordinate all system restoration activity. Internal restoration, using the
     Drop and Continue Add/Drop Multiplexers (ADMs) and Synchronous Digital
     Hierarchy (SDH) loop technology, will be automatic, with an interruption of
     less than 50 mSecs.

 .    In the case that restoration over the same cable system (Americas II)
     cannot be performed, a fall back contingency will be in place. The Embratel
     NOC will move AOL's traffic to another cable (e.g., Global Crossing,
     Atlantica-1, Americas III) as soon as possible, and in any event within 2
     hours. If, and only if, capacity on another cable is not in available, the
     Embratel NOC will move AOL's traffic over a satellite circuit as soon as
     possible, and in any event within 2 hours.

 .    In the event the international transit circuit fails, then AOL will stop
     announcing its Border Gateway Patrols ("BGPs") routes to Embratel via the
     local in-country connection. In such case Embratel will fall back to
     usingBGP routes received from from the AOL complex in the USA through
     EmbrateL'S international Internet circuits. At that time, Embratel will
     start sending AOL's dial up traffic to AOL in the USA through Embratel's
     international Internet circuits.

                                       8
                              HIGHLY CONFIDENTIAL