<PAGE>

                                                                   EXHIBIT 10.21

                        EXECUTIVE EMPLOYMENT AGREEMENT

            This Executive Employment Agreement (the "Agreement") is entered
into by and between Infonet Services Corporation, a Delaware Corporation (the
"Company") and Paul A. Galleberg, an individual (the "Executive")

                                  WITNESSETH:

            WHEREAS the Board of Directors has resolved that it is in the best
interest of the Company that its officers be subject to the terms of an
executive employment agreement; and

            WHEREAS the Company and the Executive now desire to enter into this
Agreement and set forth the terms and conditions of the Executive's employment.

            NOW, THEREFORE, in consideration of the foregoing recitals, the
mutual promises and covenants set forth below and other good and valuable
consideration, receipt of which is hereby acknowledged, the Company and the
Executive do hereby agree as follows:

                                  ARTICLE I.

                                  EMPLOYMENT
                                  ----------

Section 1.1
-----------

            The Company hereby employs the Executive to perform, on and after
November 1, 2000 or such earlier date as requested by the Chief Executive
Officer of the Company, the duties and responsibilities normally associated with
the position of Senior Vice President, General Counsel and Secretary, or such
other position to which the Executive may be promoted, for the term of this
Agreement.  Executive shall report directly to the Chief Executive Officer of
the Company and shall be the senior legal officer of the Company and its
subsidiaries and successors.  The Executive agrees to abide by the Company's
Certificate of Incorporation, its By-Laws and the direction by its Board of
Directors except to the extent such direction would be inconsistent with
applicable law.

Section 1.2
-----------

            Executive understands and agrees that, prior to a date that is not
later than November 1, 2000, the Company shall employ the Executive to perform
the duties and responsibilities normally associated with the position of
Assistant General Counsel.  Executive shall report prior to such date directly
to Ernest U. Gambaro, the Senior Vice President, General Counsel and Secretary
of the Company as of the date hereof.
<PAGE>

                                  ARTICLE II.

                                 REMUNERATION
                                 ------------

               For the first year of this Agreement, the Executive shall be paid
the Base Salary in effect on August 1, 2000. The Executive's Base Salary shall
thereafter be reviewed annually in accordance with the Company's then existing
salary review policies. The Executive shall also be entitled to receive and be
eligible to participate in those Benefits made available by the Company during
the term of this Agreement.

                                 ARTICLE III.

                       TERM AND TERMINATION OF AGREEMENT
                       ---------------------------------

Section 3.1    Term and Expiration of Agreement
-----------    --------------------------------

               This Agreement shall be effective commencing on August 1, 2000
and shall continue in effect for an initial period of 36 months ("Initial Term")
and shall thereafter be extended without further action of the parties for
additional periods of 24 months ("Extended Term") unless the Executive receives
notice from the Company not later than 24 months prior to the last day of such
Initial Term or any Extended Term of its election not to extend the Agreement.
The last day of the Initial Term or any such Extended Term shall hereinafter be
referred to as the "Expiration Date."

Section 3.2    Death or Disability
-----------    -------------------

               The Company may terminate this Agreement without any further
obligation (except as provided in this Section 3.2) to the Executive on the
Death or Disability of the Executive. If the Executive's Death or Disability
occurs in the course or as the result of the performance of his duties under
this Agreement, however, the Executive's Base Salary shall continue to be paid
to the Executive's estate or the Executive for a period of two (2) years from
the date of Death or Disability and all unvested options granted to Executive
shall vest immediately and be exercisable for the remainder of their original
term. Nothing in this Section 3.2 is intended to effect the entitlement of the
Executive or his estate to any payments or benefits to which he or it would
otherwise be entitled under any other Company plan or program.

Section 3.3    Termination for Cause
-----------    ---------------------

               The Company may terminate this Agreement at any time without any
further obligation to the Executive for Cause as defined herein.

Section 3.4    Retirement
-----------    ----------

               In the event that the Executive voluntarily elects Retirement
during the term of this Agreement, the Executive shall be entitled to the
benefits under the Company's regular Retirement program, or, if a separate
Retirement agreement has been entered into between the Executive and the Company
benefits shall be provided according to the terms of that agreement.

                                       2
<PAGE>

Section 3.5    Resignation
-----------    -----------

               The Executive is entitled to voluntarily resign his employment
with the Company during the term of this Agreement. If the Executive resigns his
employment with the Company for other than Good Reason, this Agreement shall be
deemed terminated without any further obligation of the Company to the
Executive.

Section 3.6    Termination Without Cause (The "Early Termination Option")
-----------    ----------------------------------------------------------

               The Company has the right to terminate the Executive's
employment, without cause, at any time prior to the Expiration Date by providing
the Executive with a Notice of Termination and, receipt of which, shall cause
the Company to pay the Executive the Separation Payments for the applicable
period set forth in Section 3.9 (the "Early Termination Option").

Section 3.7    Resignation for Good Reason
-----------    ---------------------------

               The Executive shall be entitled to resign his employment with the
Company for Good Reason at any time prior to the Expiration Date and receive the
Separation Payments for the applicable period set forth in Section 3.9 by
providing the Company with a Notice of Termination. The fact that the Executive
may choose not to resign his employment for Good Reason after the occurrence of
any event constituting Good Reason shall in no way affect the Executive's right
to do so upon the occurrence of a subsequent transaction or event which
constitutes a Good Reason.

Section 3.8    Stock Options
-----------    -------------

               Upon termination of the Executive's employment by Executive for
Good Reason, by the Company without Cause or by Death or Disability, all of
Executive's vested options shall continue to be exercisable for their original
term. The provisions of this Section 3.8 shall survive the expiration of this
Agreement and shall be separately provided for in the relevant option agreement
with Executive provided in connection with the option grant.

Section 3.9    Separation Payments
-----------    -------------------

               (a)  In the event the Early Termination Option is exercised by
the Company or the Executive resigns his employment with the Company for Good
Reason, the Executive shall be entitled to receive Separation Payments through
the Expiration Date or for a period of two (2) years from the effective date of
the Executive's termination or resignation, whichever period is longer, and all
unvested options granted to Executive shall vest immediately and be exercisable
for the remainder of their original term.

               (b)  Unless otherwise directed by the Executive, the Separation
Payments shall be paid or provided on a continuing monthly basis on the first
business day of each month commencing with the month immediately following the
effective date of the Executive's termination or resignation, whichever is
applicable.

               (c)  Upon the exercise of the Early Termination Option by the
Company or the Executive's resignation for Good Reason, the Executive shall be
entitled to accrue benefits (as

                                       3
<PAGE>

defined in Section 5.2) during the period the Executive receives or is entitled
to receive separation payments.

               (d)  The Company shall use the compensation which the Executive
receives or is entitled to receive as Separation Payments for the purpose of
determining the amount of any benefit to which the Executive may be entitled
under any plan or program.

               (e)  The Executive agrees that so long as he is receiving
Separation Payments, he shall not become employed by or consult with any company
whose primary business is the provision of public international value added
network services.

               (f)  The Executive agrees that so long as he is receiving
Separation Payments, he shall not induce or solicit any employee of the Company
to terminate his or her employment with the Company for any purpose.

               (g)  The Company's obligation to pay the Separation Payments and,
otherwise comply with the provisions of this Section 3.9 shall be unconditional.
The Executive shall not be required to mitigate the amount of any payment
provided for in this Section 3.9.

                                  ARTICLE IV.

                           CONFIDENTIAL INFORMATION
                           ------------------------

Section 4.1    Confidential Business Information
-----------    ---------------------------------

               The Executive agrees that he shall hold in strictest confidence
and not disclose, directly or indirectly, to any person, firm or corporation,
without the express prior written consent of the Company, any trade secrets or
any confidential business information of the Company including, but not limited
to, corporate planning, production, distribution or marketing processes;
manufacturing techniques; customer lists or customer leads; marketing
information or procedures; development work; work in process; financial
statements or notes, schedules or supporting financial data; or any other secret
or confidential matter relating to the products, sales or business of the
Company.

Section 4.2    Return of Information
-----------    ---------------------

               The Executive agrees that no later than five (5) days after his
employment is terminated with the Company he will deliver to the Company and
will not keep in his possession or deliver to anyone else, any and all drawings,
notes, memoranda, specifications, financial statements, customer lists, product
surveys, data, documents or other material containing or disclosing any of the
matters referred to in Section 4.1 above.

Section 4.3    Remedy for Breach of this Article
-----------    ---------------------------------

               The Executive acknowledges that any breach of this Article IV by
him will cause irreparable injury to the Company for which the available
remedies at law will not be adequate. Accordingly, in the event of any such
breach or threatened breach of any provision of this Article, in addition to any
other remedy provided by law or in equity, the Company shall be

                                       4
<PAGE>

entitled to appropriate injunctive relief, in any court of competent
jurisdiction, restraining the Executive from any such actual or threatened
breach of this Article. The Executive stipulates to the entry against him of any
such temporary, preliminary or permanent injunction and agrees not to resist the
Company's application for such equitable relief, except on the grounds that the
acts or omissions alleged by the Company did not violate any of the provisions
of this Article.

                                  ARTICLE V.

                                  DEFINITIONS
                                  -----------

               Whenever the following terms are used below in this Agreement,
they shall have the meaning specified below, and no other, unless the context
clearly indicates to the contrary. The masculine pronoun shall include the
feminine and neuter, and the singular the plural, where the context so
indicates.

Section 5.1    Base Salary
-----------    -----------

               "Base Salary" shall mean the Executives regular annualized rate
of pay exclusive of all other Benefits as that term is defined below

Section 5.2    Benefits
-----------    --------

               "Benefits" shall mean Benefits pursuant to this contract and all
employee welfare and pension benefit plans or programs and all other plans or
programs including, but not limited to medical and dental insurance, Infonet
Stock Incentive Plan ("ISIP"), 401(k) plans, the Infonet Supplemental Executive
Retirement Plan (the "ISERP"), bonus and incentive compensation plans, vacation
plans, etc. which the Executive or employees of the Company, and, in particular,
employees with senior management responsibility, are eligible for and entitled
to participate in, whether now in effect or added during the term of this
Agreement.

Section 5.3    Cause
-----------    -----

               "Cause" shall mean (i) the Executive's conviction of a felony or
a misdemeanor involving moral turpitude or (ii) the Executive's willful breach
or the habitual neglect of his duties under this Agreement which have a material
adverse impact on the financial condition of the Company; provided, however,
that the Company shall first have given the Executive written notice of the
alleged breach or areas of neglect and a reasonable opportunity to cure.

Section 5.4    Change in Control
-----------    -----------------

               A "Change in Control" shall be deemed to have occurred if (i) 20%
or more of the Company's outstanding securities as owned on August 1, 2000 are
sold, transferred or otherwise alienated; or (ii) after 20% or more of the
Company's outstanding securities as owned on October 19, 1994 are sold,
transferred or otherwise alienated as set forth in (i) above, any additional
securities of the Company or sold, transferred or otherwise alienated; or (iii)
the Stockholders of the Company approve a merger or consolidation of the Company
with any other corporation or entity regardless of which entity is the survivor,
other than a merger or consolidation which would result in the voting securities
of the Company outstanding

                                       5
<PAGE>

immediately prior thereto continuing to represent (either by remaining
outstanding or being converted into voting securities of the surviving entity)
at least 80% of the combined voting power of the voting securities of the
Company or such surviving entity outstanding immediately after such merger or
consolidation; or (iv) the Stockholders of the Company approve a plan of
complete liquidation or winding-up of the Company or an agreement for the sale
or disposition by the Company of all or substantially all of the Company's
assets; or (v) if the director nominees of three (3) members of the Stockholders
are not elected; or (vi) any event which the Board of Directors determines
should constitute a Change in Control.

Section 5.5    Disability
-----------    ----------

               "Disability" shall mean the Executive's absence from performance
of his assigned duties for the Company on a full-time basis for six consecutive
calendar months as a result of incapacity due to medically documented physical
or mental illness and which, in the opinion of the Executive's physician, makes
it impossible for the Executive to perform his duties and responsibilities under
this Agreement.

Section 5.6    Good Reason
-----------    -----------

               "Good Reason" shall mean the occurrence of any of the following
events without the Executive's express written consent:

               (a)  the assignment to the Executive of duties inconsistent with
the position and status of the Executive as set forth in Article I a substantial
alteration in the nature or status of the Executive's responsibilities (other
than any such alteration primarily attributable to a medical or physical
infirmity of the Executive which the Company has attempted to accommodate), or

               (b)  the failure to pay or a reduction by the Company in the
Executive's Base Salary as the same may be increased from time to time during
the term of this Agreement or the Company's failure to increase (within 12
months of the Executive's last increase in Base Salary) the Executive's Base
Salary in an amount which at least equals, on a percentage basis, the average
percentage increase in Base Salary for all key management employees within the
Company; or

               (c)  the elimination or reduction by the Company of any of the
Benefits to which the Executive is eligible for or entitled to participate in,
whether now in effect or added during the term of this Agreement or the failure
of the Company to provide the Executive with Benefits or facilities at least
comparable to those Benefits or facilities made available to other key
management employees within the Company; or

               (d)  a Change in Control; or

               (e)  any purported termination of the employment of the Executive
by the Company which is not effected according to the requirements of this
Agreement.

                                       6
<PAGE>

Section 5.7    Notice of Termination
-----------    ---------------------

               "Notice of Termination" shall mean a notice, in writing, to the
Executive from the Company or to the Company from the Executive, which states
the decision of the Company or the Executive to terminate the Executive's
employment and which (i) indicates the specific termination provision enumerated
in this Agreement relied upon, (ii) sets forth in reasonable detail the facts
and circumstances alleged to provide a basis for termination of the Executive's
employment by the Company or by the Executive and (iii) states the effective
date of the termination which shall not be less than thirty (30) days nor more
than sixty (60) days from the date of the Notice of Termination. Such notice
must be communicated to the Executive or to the Company in accordance with
Section 6.4 herein.

Section 5.8    Retirement
-----------    ----------

               "Retirement" shall mean termination of the Executive's employment
on or after the date on which the Executive attains an age and years of service
which entitles him to retire in accordance with any Retirement plan or program
provided by the Company or agreement entered into between the Executive and the
Company.

Section 5.9    Separation Payments
-----------    -------------------

               "Separation Payments" shall mean for the Executive: (i) the
average annual total monetary consideration received from the Company during the
twelve (12) month period immediately preceding the effective date of his
termination or resignation and (ii) the continuation of his Benefits.

                                  ARTICLE VI.

                                 MISCELLANEOUS
                                 -------------

Section 6.1    Action to Challenge or Enforce Agreement
-----------    ----------------------------------------

               Should either (i) the Company, its successors or assigns, or any
person acting on behalf of the Company seek to challenge this Agreement or any
of its terms in any action or legal proceeding or (ii) the Executive seeks to
enforce this Agreement or any of its terms in any action or legal proceeding,
the Company shall reimburse the Executive for all costs and attorneys' fees
incurred in connection with any such action or proceeding.

Section 6.2    Successors; Binding Agreement
-----------    -----------------------------

               The Company will require any successor (whether direct or
indirect, by purchase, merger, consolidation or otherwise) to all or
substantially all of the business and/or assets of the Company to expressly
assume and agree to perform this Agreement in the same manner and to the same
extent that the Company would be required to perform it if no such succession
had taken place. The failure of the Company to obtain such assumption agreement
prior to the effectiveness of any such succession shall be a breach of this
Agreement and shall entitle the Executive to compensation from the Company in
the same amount and on the same terms as the

                                       7
<PAGE>

Executive would be entitled to hereunder if the Executive had resigned his
employment for Good Reason.

Section 6.3    Successors and Assigns
-----------    ----------------------

               This Agreement shall inure to the benefit of, and be enforceable
by, the personal or legal representatives, executors, administrators,
successors, heirs, distributes, devisees and legatees of the Executive.

Section 6.4    Notice
-----------    ------

               Notices and all communications provided for in this Agreement
shall be in writing and shall be deemed to have been received when delivered or
mailed by United States registered mail, return receipt requested, postage
prepaid, addressed to the respective addresses set forth at the end of this
Agreement, provided that all notices to the Company shall be directed to the
attention of the President with a copy to the Secretary of the Company, or to
such other address As either party may have furnished to the other in writing in
accordance herewith, except that notice of change of address shall be effective
only upon receipt.

Section 6.5    Taxes
-----------    -----

               It is expressly understood and agreed by and between the Company
and the Executive that the Executive shall only be responsible for ordinary
income taxes should he receive payments under this Agreement. Any other excise
taxes, penalties, interest or other payments which the Executive may be required
to pay by any taxing authority shall be borne by the Company.

Section 6.6    No Waiver
-----------    ---------

               No provision of this Agreement may be modified, waived or
discharged unless in writing and signed by the Executive and such officer of the
Company as may be specifically designated or authorized by the Board of
Directors or by a Committee of the Board of Directors. No waiver by either party
hereto at any time of any breach of the other party hereto of, or compliance
with, any condition or provision of this Agreement to be performed by such other
party shall be deemed a waiver of similar or dissimilar provisions or conditions
at the same or at any prior or subsequent time.

Section 6.7    Entire Agreement
-----------    ----------------

               This Agreement represents the sole and entire Agreement among the
parties and supersedes all prior agreements, negotiations, and discussions
between the parties hereto and/or their representatives.  Any amendment to this
Agreement must be in writing specifically referring to this Agreement and signed
by duly authorized representatives of all of the parties hereto.

                                       8
<PAGE>

Section 6.8    Controlling Law
-----------    ---------------

               The validity, interpretation, construction and performance of
this Agreement shall be governed by the laws of the State of Delaware.

Section 6.9    Invalid Provision
-----------    -----------------

               The invalidity or unenforceability of any provisions of this
Agreement shall not affect the validity or enforceability of any other provision
of this Agreement, which shall remain in full force and effect.

Section 6.10   No Attack on Agreement
------------   ----------------------

               This Agreement shall not be subject to attack on the ground that
any or all of the legal theories or factual assumptions used for negotiating
purposes are for any reason inaccurate or inappropriate. The parties agree that
the language of this Agreement shall not be construed for or against any
particular party.

Section 6.11   Confidentiality
------------   ---------------

               The Executive agrees to keep confidential and not disclose any of
the terms of this Agreement to any person (including, but not limited to, any
current or former employees of the Company) other than his attorneys and/or tax
advisors unless required to do so by law.

Section 6.12   Counterparts
------------   ------------

               This Agreement may be executed in several counterparts, each of
which shall be deemed to be an original, and 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 set forth below.

INFONET SERVICES CORPORATION,                 PAUL A. GALLEBERG
a Delaware corporation

     /s/ JOSE A. COLLAZO                      /s/ PAUL A. GALLEBERG
By: _________________________________         __________________________________
Jose A. Collazo, President                    Address:

Address:                                      Paul A. Galleberg
                                              c/o Infonet Services Corporation
Infonet Services Corporation                  2160 East Grand Avenue
2160 East Grand Avenue                        El Segundo, California 90245-1022
El Segundo, California 90245-1022

              June 20, 2000                                July 3, 2000
Date: ______________________________          Date: ____________________________


                                       9