<PAGE>

                                                                   EXHIBIT 10.58

                            FULL SERVICES AGREEMENT

     This Agreement is made by McLeodUSA, and Prodigy, effective July 1, 2001
("Effective Date").  McLeodUSA and Prodigy may also be referred to as the
"Parties" or "Party" as the context allows.

In consideration of the mutual promises contained in this Agreement and other
good and valuable consideration, the Parties agree as follows:

1.   Purpose.    The following terms and conditions apply to the provision and
--   --------
use of Services provided to Prodigy by McLeodUSA as the primary provider of
Services as described in any attached addenda, exhibits, schedules and other
documents which are specifically made a part of the Agreement. The Agreement
replaces all prior agreements and understandings, whether written or oral, and
specifically the Full Service Agreement, dated June 24, 1997, the Transition
Services Agreement, dated June 24, 1997, and the Sublease Agreement, dated June
24, 1997. The Agreement Amendment for Internet Access Service Interconnection
between Prodigy Internet Services, Inc., and Splitrock dated May 31, 2000 (GSP
Amendment), as amended on July 10, 2000 (now Exhibit A to this Agreement), the
Second Agreement Amendment for Special 800 Number Service dated May 30, 2000
between Prodigy Communications Corporation and Splitrock Services, Inc. (now
Exhibit B to this Agreement), the Third Amendment between Prodigy Communications
Corporation, and Splitrock Services, Inc., dated July 10, 2000 (now Exhibit C to
this Agreement), and the May 3, 2000 letter agreement concerning prices for OC-3
connections for Prodigy's Yorktown Heights data center as provided for in
Section 28, remain in full force and effect. McLeodUSA will become Prodigy's
preferred nationwide dial access provider exclusive of Prodigy's agreements with
Southwestern Bell Corporation, provided that acceptable network performance is
maintained as required by the Agreement.

2.   Defined Terms.    The following terms are used as defined. The definitions
--   --------------
apply not only to this document but to any referenced or incorporated
attachments .

"Agreement," means this document titled Full Services Agreement and any attached
addenda, exhibits, schedules or other documents specifically referred to and
incorporated.

"End User," means a subscriber services provided by Prodigy, that are supported
by this Agreement, including services where Prodigy is the retailer or wholesale
provider of such services.

"Equipment," means a machine, including its features, conversions, upgrades,
elements, or accessories, or any combination of them.  Equipment includes all
McLeodUSA Equipment either owned or provided by McLeodUSA.  This term excludes
Programs.

"Materials," means work products (such as programs, program listings,
programming tools, documentation, reports, and drawings) that we may deliver to
you during a project.  This term does not include Programs.

"McLeodUSA," means McLeodUSA Information Services, Inc., and any references to
Splitrock or Splitrock Services, Inc.

                                       1
<PAGE>

"NAP," means a Network Access Point.

"POP," means a McLeodUSA point of presence.

"Prodigy," means Prodigy Communications Limited Partnership, and any reference
to Prodigy Communications Corporation or Prodigy Internet Services, Inc.

"Product," means a Program or Equipment.

"Program," means the following, including features and any whole or partial
copies:  (a) machine-readable instructions; (b) a collection of machine-readable
data, such as a database; and (c) related licensed materials, including
documentation and listings, in any form.  The term "Program" includes a
McLeodUSA Program and any non-McLeodUSA Program that McLeodUSA may provide to
you.  The term does not include licensed internal code or Materials.

"Services," means the network services we will provide, as more particularly
described in Section 23 of this Agreement.  Any new or additional service not
contemplated by this Agreement will not be a part of this Agreement until the
terms, conditions, and prices of the service are confirmed in a Transaction
Document.  Services provided to you under this Agreement shall include reports,
surveys and analysis reasonably required to fulfill the purposes of this
Agreement, which shall not be subject to any additional charge.

"System," means the Services and Products that McLeodUSA identifies in writing
as a System.

"Transaction Document," means a document or documents provided by McLeodUSA
before a business transaction under the Agreement occurs that confirms the
details of the transaction, and which will not be effective unless and until the
Parties agree in writing to its contents.

"User Identification," means a code or codes that enable authorization or access
to programs, data or equipment through Services.

"Yorktown Heights," means Prodigy's data center located in Yorktown Heights, New
York.

3.   Term.    This Agreement is in effect for thirty-six (36) months from the
--   -----
Effective Date. The Agreement will automatically renew for successive one (1)
year terms beginning July 1, 2004, and each July 1 thereafter, unless a Party
provides written notice of termination at least six (6) months prior to the end
of the then current term. However, if McLeodUSA is acquired by any of the
following entities or their affiliates or successors (AT&T, MCI WorldCom,
AOL/Time Warner, Earthlink, Sprint or Microsoft), Prodigy in its sole discretion
has the right to accelerate termination of this agreement upon ninety (90) days
prior written notice.

4.   Orders for Services or a Product.    Prodigy may order Services or a
--   ---------------------------------
Product in writing delivered by hand, mail or facsimile. The order is accepted
and becomes subject to this Agreement when McLeodUSA provides Prodigy with a
Transaction Document, which accepts expressly and precisely the terms of the
order. Prodigy shall indicate its acceptance of any additional terms in a
Transaction Document or attachment by signing the document and returning it to
McLeodUSA.

5.   Electronic Communications.    The Parties may communicate with the other
--   --------------------------
by electronic means for information purposes only, such as through electronic or
Prodigy

                                       2
<PAGE>

Mail. Any electronic communication must be followed by written confirmation or
be telecopied in order to be binding on either party. Documents, which include
handwritten signatures, may be transmitted by telecopier, and shall be deemed
binding without the need for original signatures, although original signature
copies are preferred.

6.   Prices.    By executing this Agreement, Prodigy commits to pay McLeodUSA
--   -------
minimum monthly revenue of four million five hundred thousand dollars ($4.5M) in
the following manner:  (a) a fixed, recurring one million dollars ($1M) network
access charge regardless of traffic or usage, and (b) a traffic or usage based
charge of three million five hundred thousand dollars ($3.5M).  The traffic or
usage based revenue will be calculated on market specific hourly rates and
minimum traffic or usage commitments per POP as provided for in Schedule 25.1 to
this Agreement.  Schedule 25.1 may be modified from time to time consistent with
this Agreement.  If new products or services are added, the prices will be
stated in the applicable Transaction Document.  Unless specifically agreed to in
writing, no additional charges shall be imposed or incurred for Services under
this Agreement.  McLeodUSA shall provide Services to Prodigy at prices no less
favorable than similar Services are sold to any other customer of McLeodUSA
under similar terms and conditions governed by the customer's credit worthiness,
the term of the Services, pricing structure, geographic coverage, perfomance
requirements, and related credits and minimum financial commitments (in
aggregate and by POP).  NAP fees previously charged by McLeodUSA under prior
agreements will be discontinued upon the Effective Date of this Agreement.

7.  Payment and Taxes.    (a) Prodigy shall pay:  (1) usage and recurring
--  ------------------
charges as provided for in the Agreement; and (2) all other charges when or
after they are incurred.  Amounts due are payable as specified in the invoice,
which invoice shall be consistent with the terms of this Agreement.

(b) Prodigy agrees to pay any tax on the Services provided except as provided
below. Prodigy is responsible for personal property taxes for each Product
purchased and each Program licensed to you from the date the Product or Program
is shipped or otherwise made available.  Prodigy shall be responsible for sales,
use, property, and other taxes on machines, software, or goods and services
provided by it.

(c) McLeodUSA shall be responsible for payment of sales, use, property, and
other taxes on machines, software, or goods and services used or furnished by
McLeodUSA for its own use in providing the Services to Prodigy.  All taxes
incurred in connection with the upgrade of the network to ATM switching, or any
other upgrade, whether mandatory or voluntary, shall be the sole responsibility
of McLeodUSA.

(d) Taxes, as used in this Agreement, shall not include any FCC charges or other
charges payable to any government organization other than a taxing authority,
all of which McLeodUSA shall pay.

(e) McLeodUSA shall make reasonable efforts to provide invoices on or before the
tenth day of the month following the monthly period being invoiced and Prodigy
agrees to pay invoices within thirty (30) days of the invoice date.  Prodigy
agrees to make payment by wire funds transfer.  If Prodigy fails to make
payments by the applicable invoice date, it agrees to pay a service charge equal
to the lesser of 1.5% per month or the maximum allowable rate under applicable
law on each unpaid amount.

                                       3
<PAGE>

8.  Patents and Copyrights.    (a) Claim. For purposes of this Section only, the
--  -----------------------        ------
term "Product" includes Materials alone or in combination with Products provided
as a System.  If a third party claims that a Product McLeodUSA provides to
Prodigy infringes that party's patent or copyright, McLeodUSA will defend
Prodigy against that claim.  McLeodUSA will pay all costs, damages, and
attorney's fees, provided that Prodigy:  (1) promptly notifies McLeodUSA in
writing of the claim; and (2) with its full cooperation, allows McLeodUSA to
control the defense of any claim and any related settlement negotiations.  At
Prodigy's option and at its cost, Prodigy may retain its own counsel to advise
it with regard to the cooperative efforts with McLeodUSA.  If a claim is made or
appears likely to be made, McLeodUSA will take reasonable steps, and Prodigy
agrees to permit McLeodUSA to do so, to enable Prodigy to continue to use the
Product, or to modify it, or replace it with one that is at least functionally
equivalent.  If McLeodUSA determines that none of these alternatives is
reasonably available, Prodigy agrees to return the Product to McLeodUSA upon
written request and McLeodUSA may terminate the affected Product at no further
charge to Prodigy, in which case McLeodUSA will refund to Prodigy the unused
prorata portion of any advance payments for the Product.

(b) PRODIGY AGREES THAT ITS RIGHTS, AS PROVIDED BY THIS SECTION REGARDING ANY
CLAIM OF INFRINGEMENT ARE LIMITED AND THE REMEDIES IN THIS SECTION WILL BE YOUR
SOLE AND EXCLUSIVE REMEDY FOR ANY SUCH CLAIM.

(c) Notice of Infringement. All notices of patent or copyright infringement
---------------------------
permitted or required by this Agreement will be in writing and will take effect
upon receipt.

(d) Claims for Which McLeodUSA is Not Responsible. McLeodUSA has no obligation
    ----------------------------------------------
regarding any claim to the extent it is based on any of the following:  (1)
Prodigy's modification of a Product, or a Program's use with equipment and
programs other than the Equipment and Programs with which the Program is
designed to operate; (2) the combination, operation, or use of a Product with
any product, data, or apparatus that McLeodUSA did not provide unless McLeodUSA
had written notice and acknowledged in writing receipt of notice that the
intended use of the Product was for a use with a product, data, or apparatus we
did not provide; or (3) infringement by a non-McLeodUSA Product alone, as
opposed to its combination with Products McLeodUSA provides as a System.

9.  Limitation of Liability.    (a) Circumstances may arise where, because of a
--  ------------------------
McLeodUSA default or other liability, Prodigy is entitled to recover damages.
Except for indemnification and failure to meet performance standards and service
level credits, in each such instance, regardless of the basis on which Prodigy
is entitled to claim damages, McLeodUSA is liable only for:  (1) payments
referred to in our patent and copyright section described above; (2) bodily
injury (including death), and damage to real property and tangible personal
property; and (3) the amount of any other actual loss or damage, in excess of
$100,000 or the charges (if recurring or usage, 12 months' charges apply) for
the Service or Product that is the subject of the claim.  This limit also
applies to any McLeodUSA subcontractors, agents and Program developers.  It is
the maximum for which McLeodUSA, its subcontractors, agents and program
developers are collectively responsible.

                                       4
<PAGE>

(b) Items for Which Neither Party is Liable. Under no circumstances are either
    ----------------------------------------
Party or its subcontractors, agents or Program developers liable for any of the
following:  (1) third-party claims against a Party for losses or damages (other
than those under (a)(1) and (a)(2) in this Section) except for willful acts or
acts of gross negligence; (2) loss of, or damage to, records or data except for
any actual loss or damage willfully and intentionally caused by a Party or
caused by gross negligence, subject to the limitation contained in (a)(3) of
this Section; or (3) economic consequential damages (including lost profits or
savings) or incidental damages, even if either Party is informed of their
possibility.

(3) EACH PARTY AGREES THAT ITS RIGHTS ARE LIMITED BY THIS SECTION, THAT THE
LIMITATIONS PROVIDED HEREIN ARE FAIR AND EQUITABLE, AND EACH PARTY HEREBY WAIVES
ANY RIGHT OR REMEDY IT MAY HAVE FOR THE RECOVERY OF ANY OTHER DAMAGES.

10.  Additional Rights.    Prodigy may have additional rights under certain laws
---  ------------------
(such as consumer laws) which do not allow the exclusion of implied warranties,
or the exclusion or limitation of certain damages.  If these laws apply,
McLeodUSA's exclusions or limitations may not apply to Prodigy.

11.  Geographic Scope.    All of your rights, all our obligations, and all
---  -----------------
licenses are valid only in the fifty (50) United States.

12.  Governing Law.    This Agreement shall be governed by and interpreted under
---  --------------
the laws of the state which is the domicile of the party who is an initial
defendant in any action or the party upon whom an initial demand for arbitration
is served.  Any action or arbitration proceeding shall be brought in the state
or federal courts located in that same state.

13.  Notices.    All notices or other communications shall be deemed to have
---  --------
been given when made in writing and either: (a) delivered in person; (b)
received within twenty-four (24) hours after delivery to an agent, such as an
overnight or similar delivery services; all delivery services prepaid; or (c)
received within 72 hours after deposited in the United Sates mail, postage
prepaid, and addressed as follows:

McLeodUSA                               Prodigy
---------                               -------

McLeodUSA Information                   Prodigy Communications,
Services, Inc.                          Limited Partnership
15 East 5th Street                      6500 River Place Boulevard
Suite 1800                              Building III
Tulsa, OK  74103                        Austin, TX  78730
ATTN:  Contract Administration          ATTN:  President

With copies to:
---------------
McLeodUSA Telecommunications            Prodigy's General Counsel
Services, Inc.                          Same address as above
Attn: Law Group
McLeodUSA Technology Park
P.O. Box 3177
Cedar Rapids, IA 52406-3177

                                       5
<PAGE>

Or at such other addresses as the Parties may from time to time in writing
designate.  If notice is provided by overnight mail, the address is 6400 C
                                     --------------                 ------
Street SW, Cedar Rapids, Iowa 52404.  Except where the context otherwise
-------------------------------------
indicates, all notices and documents shall be deemed to have been given on the
day received.

14.  Financial Covenants.    From the Effective Date and during the term of this
---  --------------------
Agreement, McLeodUSA covenants and agrees that it will:

(a)  Provide financial and other information consisting of:  (1) Annual
                                                                 ------
Financial Reports. Provide upon request of Prodigy a copy of McLeodUSA's 10-K
------------------
filed with the SEC. In addition, McLeodUSA shall provide immediate notice to
Prodigy in the event that it receives an qualified opinion concerning its
ability to continue as a going concern and/or the likelihood of any substantial
impairment of its assets. In the event that McLeodUSA ceases to be a public
company required to file a 10-K, then within ninety (90) days after the close of
each calendar year, a balance sheet as of the end of McLeodUSA's fiscal year, a
statement of operations and statement of cash flows.

(2) Quarterly Financial Statements. Provide upon request of Prodigy a copy of
    -------------------------------
McLeodUSA's latest 10-Q filed with the SEC.  In the event that McLeodUSA ceases
to be a public company required to file a 10-Q, then within ninety (90) days
after the close of each quarter, a balance sheet as of the end of the quarter, a
statement of operations and statement of cash flows.

(3) Payables.  Not later than forty-five (45) days after the close of each
    ---------
calendar quarter, beginning with the quarter commencing July 1, 2001, a total of
amounts which are due and payable and have not been paid by their contractual
due date, and a list of each creditor to which payments over $500,000 are due.

(4) Taxes.  Prompt payment without interest or penalty, all taxes, assessments
    -----
and similar imposts and charges of every kind and nature lawfully levied,
assessed or imposed upon McLeodUSA, except to the extent being contested in good
faith and furnish Prodigy evidence of such payment on a quarterly basis within
forty-five (45) days after the close of each calendar quarter.

(5) Liens and Litigation.  Notice, within ten (10) days of receipt of notice of
    ---------------------
any lien or lawsuit which is threatened or pending against McLeodUSA and which
involves a claim in excess of $1,000,000.

(6) Projections.  Within thirty (30) days after receipt of forecasts required by
    ------------
the Agreement for each applicable quarter, plans and projections for income,
expenses, capital receipt and expenditure, for the immediately succeeding
fifteen (15) month period.  Included with the statements to be provided
quarterly pursuant to this Section, McLeodUSA shall also provide evidence of
results as compared to past projections, which shall also be certified as true
by its chief executive or financial officer.

(7) Delisting.  Written notice of any delisting of McLeodUSA stock by the NASDAQ
    ----------
stock exchange within ten (10) days from notice of the delisting.

                                       6
<PAGE>

(8) Confidentiality.  Written notice where McLeodUSA used customer use patterns
    ----------------
in violation of this Agreement's confidentiality provisions to compete or to
assist others to compete against Prodigy.

(b) Maintain valid and effective insurance policies that cover McLeodUSA
properties and risks of the business in such types and amounts as are consistent
with customary practices and standards of companies engaged in businesses and
operations similar to Prodigy's and furnish not later than 45 days after the
close of each calendar quarter, beginning with the quarter commencing July 1,
2001, certificates evidencing such insurance.  After the receipt of such
certificate, Prodigy may request that McLeodUSA obtain additional coverage,
consistent with reasonable business practices which McLeodUSA shall obtain.

15.  Headings.    The headings contained herein are inserted for convenience or
---  ---------
reference only and are not intended to be part of or to affect the meaning or
interpretation of this Agreement.

16.  Mutual Responsibilities.    The Parties agree that: (a) neither party
---  ------------------------
grants the other the right to use its trademarks, trade names, or other
designation in any promotion or publication; (b) all information exchanged by
both parties is not confidential unless such information is conspicuously marked
as confidential and is managed as otherwise provided for in this Agreement; (c)
each Party grants the other only the licenses specified. No other licenses
(including licenses under patents) are granted; (d) each Party will promptly
notify the other if it becomes aware of any unsafe conditions or hazardous
materials to which the other's personnel would be exposed at any of its
facilities; (e) NEITHER PARTY WILL BRING A LEGAL ACTION OR REQUEST ALTERNATIVE
DISPUTE RESOLUTION MORE THAN TWO YEARS AFTER THE CAUSE OF ACTION AROSE UNLESS
SUCH CLAIM IS AS A RESULT OF A THIRD PARTY CLAIM, IN WHICH EVENT THE TWO YEAR
PROVISION SHALL NOT APPLY; (f) neither Party is responsible for failure to
fulfill its obligations (other than payment obligations) due to causes beyond
its reasonable control, including without limitation, acts of God, war, riots,
blockades, insurrections, labor disputes, lockouts, earthquakes, fires, storms,
lightning, power failures, floods, natural disasters, accidents, new or changed
governmental regulations or laws, or other similar events beyond the reasonable
control of the party relying on this provision of the Agreement ("Force
Majeure"); and (g) each Party will comply with all applicable laws regulations
or conventions including those related to data privacy, international
communications and exportation of technical or personal data. Each Party is
responsible for obtaining all necessary governmental regulatory or statutory
approvals for the offering of any services.

17.  McLeodUSA Responsibilities.    McLeodUSA will: (a) not assign, or otherwise
---  ---------------------------
transfer, this Agreement, or its rights or obligations under it, or delegate its
rights or Prodigy's obligations, other than to a McLeodUSA affiliate, without
Prodigy's prior written consent, which consent will not be unreasonably
withheld, provided, however, that McLeodUSA will be able, without Prodigy's
consent, to assign any rights and delegate any duties contained in this
Agreement to any entity into which McLeodUSA may be merged or consolidate or
which purchases all or substantially all of its assets; (b) obtain, install and
maintain suitable equipment as necessary to provide the

                                       7
<PAGE>

Services; (c) fulfill all regular activity and performance reporting and
analysis, including service disruption analysis, periodic audits, and attend and
participate actively in monthly status meetings which shall be held no less
frequently than monthly between the Parties; and (d) be responsible for data,
programs or other material that McLeodUSA provides for use with the Service.

18.  Prodigy Responsibilies.    Prodigy agrees: (a) not to assign, or otherwise
---  -----------------------
transfer, this Agreement or Prodigy's rights under it, or delegate Prodigy's
rights without prior written consent of McLeodUSA, which consent will not be
unreasonably withheld, provided however, that Prodigy will be able, without the
consent of McLeodUSA, to assign this Agreement or to assign any rights or
delegate any duties contained in this Agreement to an affiliate of Prodigy; (b)
to allow McLeodUSA to install mandatory engineering changes (such as those
required for safety) on Equipment; (c) that it is responsible for the results
obtained from the use of the Services and Products; (d) to provide McLeodUSA
with sufficient, and safe access to Prodigy facilities for McLeodUSA to fulfill
its obligations during reasonable hours and under such conditions as Prodigy may
reasonably impose; (e) to control and be responsible for issuance of User
Identifications and their distribution to End Users; (f) to be responsible for
data, programs, or other material that Prodigy provides for use with a Service;
(g) that McLeodUSA has no liability to those whom Prodigy authorizes to access a
service; (h) that McLeodUSA is not responsible for any data or text not
generated by McLeodUSA, including the content and accuracy, which is received,
routed or sent as a result of the Services McLeodUSA provides; and (i) that
McLeodUSA is free to enter into any agreements with third parties that are
similar or dissimilar to this Agreement without Prodigy's consent or approval.

19.  Warranty of Services.    (a) McLeodUSA warrants that it will provide
---  ---------------------
Services in a workmanlike manner, consistent with industry standard according to
its current Services description contained in the Agreement, any attachment or
Transaction Document, and in a manner so that the Services and the network shall
be compatible with Prodigy's equipment.

(b) OTHER THAN AS EXPRESSLY PROVIDED IN THE AGREEMENT, MCLEODUSA DISCLAIMS ALL
WARRANTIES, INCLUDING THE IMPLIED WARRANTY OF MERCHANTABILITY, FITNESS FOR A
PARTICULAR PURPOSE, AND NON-INFRINGMENT.

20.  Items Not Covered by Warranty.    McLeodUSA does not warrant uninterrupted
---  ------------------------------
or error-free operation of a Service or Product. McLeodUSA will specifically
identify Services and Products that have a warranty, other than as described in
this and Section 19, and the terms of that warranty. Unless McLeodUSA specifies
otherwise in this Agreement it provides Materials, non-McLeodUSA Services and
non-McLeodUSA Products on an "AS IS" basis without any warranty from McLeodUSA.
Non-McLeodUSA manufacturers, suppliers, or publishers may provide their own
warranties.

21.  Equipment Provided by McLeodUSA.    Any Equipment installed on a Prodigy
---  --------------------------------
premises for purposes of providing services is and will remain a McLeodUSA asset
or that of any lessor, and will not become a fixture or realty.  Any Equipment

                                       8
<PAGE>

containing licensed internal code will identified to you.  No right, title, or
interest in or to the Equipment, or licensed internal code associated with it,
or any related planning information, is conveyed to Prodigy although the
Equipment is used to provide Services to you.

22.  Confidentiality.    (a) McLeodUSA agrees not to disclose Prodigy
---  ----------------
confidential information, including programs and data transmitted using the
Services and usage forecasts as described in this Agreement, nor shall McLeodUSA
disclose or use Prodigy customer private information, such as name, address,
credit card or other information which may be transmitted using the Services.
Geographic service usage patterns are also considered to be confidential and
shall not be used by McLeodUSA to directly compete with Prodigy or to assist
others in competing directly with Prodigy. McLeodUSA has no obligation of
confidentiality relating to Prodigy or its information which is not confidential
or which Prodigy does not conspicuously mark as confidential. McLeodUSA
acknowledges that all Prodigy customer information, and information about
Prodigy individual customers is confidential. Information that is not
confidential includes information which is: (1) either currently publicly
available or becomes publicly available in the future without a McLeodUSA breach
of any obligation or responsibility described in this Agreement; (2) rightfully
received by either Party from a third party, where the information was received
without any obligation of confidentiality associated with it; (3) already in a
the possession of McLeodUSA without an obligation of confidentiality; (4)
independently developed by McLeodUSA; (5) approved for disclosure by Prodigy; or
(6) treated by Prodigy as non-confidential.

(b) McLeodUSA has no liability for any disclosure of information that occurs as
the result of its delivery of Prodigy information, at Prodigy's direction and to
a recipient Prodigy designates, when the delivery is made in the normal course
of Services provisioning (for example, to an incorrect delivery address provided
by Prodigy to McLeodUSA).  McLeodUSA may disclose information to the extent
required by law, but will give Prodigy as much advance notice of such potential
disclosure as reasonably possible.

(c) McLeodUSA will handle Prodigy information marked confidential in a
confidential manner, and Prodigy will not permit McLeodUSA confidentially marked
information to be disclosed.  Prodigy is responsible for developing and
maintaining reasonable and customary procedures, which will notify Prodigy of
any material security breach that affects the Services.  Prodigy agrees that any
information regarding a McLeodUSA security system will be McLeodUSA confidential
information.  For the purposes of operation and maintenance, McLeodUSA may use,
copy, store, and distribute internally Prodigy information but only to the
extent necessary for operation and maintenance.  McLeodUSA shall have no such
rights with respect to Prodigy customer information, or with respect to
information about Prodigy customers.  McLeodUSA agrees not to reverse assemble
or reverse compile Prodigy information.  McLeodUSA will use reasonable
procedures, but McLeodUSA does not guarantee that these procedures will prevent
the loss, alteration of, or improper access to, Prodigy information.  Prodigy
agrees that access to Prodigy information will not prohibit or prevent McLeodUSA
from developing or marketing any service or product so long as McLeodUSA does
not violate the confidential provisions of this Agreement.  For transmissions
carried over interexchange

                                       9
<PAGE>

carriers' and local exchange carriers' facilities, McLeodUSA is not responsible
for transmission errors, or corruption or security of data.

23.  Services Description.    McLeodUSA will provide Services consisting of the
---  ---------------------
following components:  (a) dial access network as described in Section 23.1; and
(b) regional servers connectivity as described in Section 23.2.

23.1  Dial Access Network.  (a) McLeodUSA will provide dial access for data
----  --------------------
transport for Prodigy End Users (for purposes of this section "Service").
McLeodUSA will provide this Service to Prodigy in all locations in which, on the
Effective Date of this Agreement, such dial access service already exists.

(b) The Service will be provided to all current dial access locations listed on
Schedule 25.1 to this Agreement plus other locations as McLeodUSA builds,
acquires new facilities, or has dial access facilities presently.  McLeodUSA may
substitute a new POP for an existing POP upon thirty (30) days prior notice of
the change and with sixty (60) days simultaneous usage so long as McLeodUSA
provides porting of the traffic to the new site.  Prodigy may request new sites
for local dial access; but McLeodUSA will not be obligated to provide dial
access Service in any new dial access location with usage in any month of less
than five thousand (5,000) dial hours unless McLeodUSA reviews the location for
the new site and approves the creation of a new site at such location, in its
sole discretion.  Within ninety (90) days of execution of this Agreement,
McLeodUSA will evaluate expanding its dial access coverage for all Prodigy
customers and provide Prodigy with pricing for such expansion on a per city rate
basis.  McLeodUSA can modify the site coverage only with Prodigy's permission,
unless the modification is for a substitution of existing coverage, in which
case McLeodUSA does not need Prodigy's permission but any new access number
added must be coordinated with Prodigy so that Prodigy's customers can be given
adequate notice of the change.  Any new dial access sites added by McLeodUSA for
Services will be available to Prodigy, if Prodigy chooses to use them.  The
Parties agree to discuss within a commercially reasonable timeframe, and from
time to time whether they should eliminate any of the POPs identified in
Schedule 25.1 due to underutilization or to provide a reduction in cost to
either party.  If the Parties agree that those locations should be eliminated,
McLeodUSA agrees to arrange for porting of those dial access numbers to another
provider of Prodigy's choice when technically and economically feasible.

(c) The Service shall include the receipt of inbound data dial traffic from
Prodigy's End Users and the muting of such traffic to another End User, to a
regional server, to Prodigy's data center at Yorktown Heights, or to the
selected Internet NAPs.  McLeodUSA will not support initiating a call to another
End User's telephone.  McLeodUSA shall, in its sole discretion, decide the
number of dial ports it provides to service each site, as well as the method it
uses to provide Service to each site provided the grades and performance
standards of service as set forth in this Agreement are met.  Examples of
methods McLeodUSA may use to provide this Service include:  (1) a physical site
presence with modem ports; or (2) a virtual presence using call forwarding or a
foreign exchange.

(d) All new access equipment provided by McLeodUSA will have speed capacity with
respect to backbone access, and with respect to End User access, consistent with
the

                                       10
<PAGE>

service that can and will be provided from that site.  McLeodUSA shall be
responsible for:  (1) inbound communications facilities (such as hunt groups,
measured business lines or DID trunks); (2) modem hardware including ports and
chassis; and (3) network equipment and communications facilities to transport
traffic from the McLeodUSA dial site to other sites, to Prodigy's data center at
Yorktown Heights and any NAPs.

(e) McLeodUSA shall transport the dial data traffic to Prodigy via TCP/IP over
ATM.  McLeodUSA will not change the terms or conditions of a Service without
Prodigy's approval, which Prodigy agrees will not be unreasonably withheld.

23.2.  Regional Servers.  Prodigy may provide, maintain and manage regional
-----  -----------------
servers at sites determined by Prodigy, which are to be geographically dispersed
and co-located at McLeodUSA network hub sites ("Regional Servers").  Such
equipment is limited to that which may be installed in a standard 19" rack per
site.  Prodigy shall provide, maintain and manage diagnostic equipment,
connection equipment that Prodigy may use to connect to McLeodUSA and associated
analog phone lines which Prodigy may use to manage Prodigy's Regional Servers.
In addition, Prodigy shall provide the electric power cables and the equipment
connection cables for the equipment Prodigy provides, including those cables,
required to connect Prodigy's equipment to McLeodUSA network equipment.  Prodigy
also agrees to comply with all safety requirements at each site.  Each Regional
Server will be Ethernet connected to the McLeodUSA network.  Neither McLeodUSA
nor any other McLeodUSA customer shall use Prodigy's Regional Servers for any
purpose except to support Prodigy's End Users.  McLeodUSA shall provide Prodigy
with access to McLeodUSA sites for the purpose of maintaining, upgrading and
servicing these Regional Servers at no additional cost to Prodigy.  Prodigy is
responsible for separately procuring from McLeodUSA the upstream connection from
the Regional Server.  The upstream connection is defined as the network
facilities used to transport traffic from the Regional Server to locations other
than the source dial node (such as Yorktown Heights or the Internet).  Cost for
such services will be negotiated if Prodigy wishes to deploy Regional Servers.
The Regional Servers will not be included in the service level objectives, as
provided in Section 24.

23.3.  V.92 Capability.  McLeodUSA will use commercially reasonable efforts to
-----  ----------------
provide support for v.92 modems within 120 days of an acceptable software
release of this feature from Nortel or other modem equipment partner used by
McLeodUSA (defined as either acceptable to McLeodUSA or a release that has been
commercially deployed) for the current modem platform(s) deployed in the
McLeodUSA network.  Both parties understand that the above time frame may be
extended for hardware or software issues associated with v.92 that may delay
implementation.

24.  Performance
---  -----------

24.1  Performance Standards.  McLeodUSA will have performance standards
----  ----------------------
objectives for End User-services as follows:

(a) Individual POP `24-hours' Call Failure Rate. For each individual access
    --------------------------------------------
number given to any End User, the Average 24-hours Call Failure Rate during a
month shall not exceed ten percent (10%) for the immediately succeeding two (2)
consecutive months and the

                                       11
<PAGE>

parties determine that the reason such rate exceeded 10% was not due to
Scheduled Maintenance. This Call Failure Rate is based on a minimum sample size
of eight thousand (8,000) calls per access number. At least thirty percent (30%)
of the subscribers using a particular access number will have IP Insight client
loaded in their software.

(b) Individual POP `Evening Hours' (6pm - 12am) Call Failure Rate. For each
    --------------------------------------------------------------
individual access number given to any End User, the Average Evening Hours Call
Failure Rate during a month shall not exceed thirteen percent (13%) for the
immediately succeeding two (2) consecutive months. This Call Failure Rate is
based on a minimum sample size of two thousand (2,000) per access number.  At
least thirty percent (30%) of the Subscribers using a particular access number
have IP Insight client loaded in their software.

(c) Individual POP `24-hours' Latency.  For each POP, the monthly median round
    ----------------------------------
trip ping times shall not be greater than three hundred (300) milliseconds.  The
measurement is the computed median ping time based on the aggregate of Active
Tests within the McLeodUSA Network infrastructure for a month with a minimum
sample size of two thousand (2,000) per POP.  The POPs to be sampled will be
mutually agreed upon and variable, starting with the Inverse Benchmark POPs.

(d) Individual POP `Evening Hours' Latency.  For each POP, the Evening Hours
    ---------------------------------------
monthly median round trip ping times shall not be greater than three hundred
fifty (350) milliseconds. The measurement is the computed median ping time based
on the aggregate of all Active Tests within the McLeodUSA Network infrastructure
for a month with a minimum sample size of four hundred (400) per POP.

(e) Rules Governing Performance Standards.  Performance Standards are based on
    --------------------------------------
an access number by access number basis.  Performance Standards are determined
upon the accuracy of Prodigy's four-month rolling monthly access number
forecast.  To the extent that Prodigy's access number forecast is inaccurate by
more than ten percent (10%), the Performance Standards shall not apply.  Insight
Data for Performance Standards will be collected by Prodigy the first Monday on
or after the fifth (5th) calendar day of each month.  Prodigy will provide
McLeodUSA access to IP Insight metrics via means defined in the existing
agreement Prodigy has with Visual Networks.  McLeodUSA and Prodigy agree to
jointly meet with the company responsible for IP Insight testing within sixty
(60) days after execution of the definitive agreement.  If any benchmark or
other measurement device as specified in this Agreement is discontinued either
by the provider or by contract termination, the Parties shall mutually agree
upon a replacement metric or system.

24.1.1  Definitions.  For purposes of this Section the following definitions
------  ------------
apply:

(a) "24 hours," means the full 24 hours of local time for the Prodigy's End
User.

(b) "Active Test," means network latency measures (pings) provided by Visual
Networks, Inc. measured from the McLeodUSA NASs to an interface router at a
point in Prodigy's network data center in Yorktown Heights and the routers at
the active peering points in McLeodUSA's network.

(c) "Average," means averages for individual access numbers that are calculated
using all samples collected by the reporting tools for a specific access number
during that month.

(d) "Call Failure Rate," means a combination of the busy and ring-no-answer
categories provided by the IPInsight client and management reporting tools.

(e) "CSV File," means a common separated variable file.

(f) "Evening hours," means from 6pm to 12am local time for the Prodigy End User.

                                       12
<PAGE>

(g) "Inverse Benchmark," means a product of Visual Networks, Inc. that is a
monthly comparison of the performance of ISPs and wholesale access vendors.

(h) "IPInsight," means a product of Visual Networks, Inc., that is a part of
Prodigy's access kit.  IPInsight collects information about End User PC
configuration, connectivity and throughput, and forwards that information to
Prodigy. IP Insight collects information about call failures and latency that is
used in the Performance Standards.

(i) "Latency," means circuit latency measured by pings performed from McLeodUSA
Network Points to specified targets in the McLeodUSA network.  McLeodUSA and
Prodigy will mutually agree upon all targets.  The starting set will be based
upon the POPs used in the monthly Visual Networks Inverse Benchmark test, or at
significant peering points in the McLeodUSA backbone network.

(j) "NAS," means network access server.

(k) "NOC," means network operation center.

(l) "PETS," means the Prodigy Event Tracking System.

(m) "Scheduled Maintenance," means the time period during which all scheduled
maintenance shall occur and shall be between 2 am and 5 am local time (where the
NAS is located).  McLeodUSA will notify Prodigy's data NOC of regularly
scheduled outages which directly effect Prodigy Internet customers ability to
login (authenticate) to a POP or the ability to navigate `the Internet' not less
than five (5) days in advance unless extenuating circumstances arise which
require McLeodUSA to take the necessary and prudent steps to maintain the
integrity of the dial-access and transport network on which Prodigy traffic is
carried.

24.2  Performance Standards Credits.
----  ------------------------------

(a)  Service Level Agreement Credits for Individual POP `24-hours' Call Failure
     --------------------------------------------------------------------------
Rate:  (1) A minimum of eight thousand (8000) call records must be received for
-----
each access number; (2) The application of service level credits are tied to
Prodigy's four-month rolling monthly forecast accuracy by Dial Access Number. To
the extent that Prodigy exceeds the Dial Access Number forecast by more than ten
percent (10%), the service level credits shall not apply for that number; (3) A
maximum of ten percent (10%) 24-hour Call Failure Rate is considered allowable;
(4) Credits are assessed per access number for all calls in any access city and
are expressed as a percentage above of the 24-hour allowable Call Failure Rate;
(5) Performance credits for service may only be applied during the month that
the Performance credits are earned; (6) Prodigy must request Performance credits
within thirty (30) days of the end of the monthly measurement period.

                                       13
<PAGE>

                              Credit Rate Table I

           1) Minimum of eight thousand (8,000) calls for the month

            2) Ten percent (10%) or greater Total Call Failure Rate

           3) Credit Rate = % of Monthly Invoice For the Failed City

            4) # of access numbers (in sample range) X Credit Rate

    5) At least thirty percent (30%) of the Subscribers using a particular
        access number have IP Insight client loaded in their software.

<TABLE>
<CAPTION>
    # of Sample Ranges               Credit Rate
    ------------------               -----------
    <S>                              <C>
     8,000 to 43,999 -                    .11%
     44,000 to 79,999 -                   .33%
     80,000 to 115,999 -                  .55%
     116,000 to 151,999 -                 .77%
     152,000 to 187,999 -                 .99%
     188,000 to 223,999 -                1.11%
     224,000 to 259,999 -                1.33%
     260,000 + -                         1.55%
</TABLE>

(b) Service Level Agreement Credits for Individual POP `Evening Hours (6pm -
    ------------------------------------------------------------------------
12am)' Call Failure Rate.  (1) A minimum of two thousand (2000) call records
-------------------------
must be received for each access number; (2) The application of service level
credits are tied to Prodigy's four (4) month rolling monthly forecast accuracy
by Dial Access Number.  To the extent that Prodigy exceeds the forecast by more
than ten percent (10%), the service level credits shall not apply for that
number; (3) A maximum of thirteen percent (13%) Evening Hour Call Failure Rate
is considered allowable; (4) Credits are assessed per access number for all
calls in any access city and are expressed as a percentage above the allowable
Evening Hour Call Failure Rate; (5) Performance credits for service may only be
applied during the month that the Performance credits are earned; (6) Prodigy
must request Performance credits within thirty (30) days of the end of the
monthly measurement period.  Calls in any access city and are expressed as a
percentage above the allowable Evening Hour Call Failure Rate.

                                       14
<PAGE>

                              Credit Rate Table II

            1) Minimum of two thousand (2,000) calls for the month

         2) Thirteen percent (13%) or greater Total Call Failure Rate

           3) Credit Rate = % of Monthly Invoice For the Failed City

            4) # of access numbers (in sample range) X Credit Rate

    5) At least thirty percent (30%) of the Subscribers using a particular
        access number have IP Insight client loaded in their software.

<TABLE>
<CAPTION>
    # of Sample Ranges              Credit Rate
    ------------------              -----------
    <S>                              <C>
     2,000 to 10,999 -                  .11%
    11,000 to 19,999 -                  .33%
    20,000 to 28,999 -                  .55%
    29,000 to 37,999 -                  .77%
    38,000 to 46,999 -                  .99%
    47,000 to 55,999 -                 1.11%
    56,000 to 64,999 -                 1.33%
    65,000 + -                         1.55%
</TABLE>

(c) Additional Performance Standard notification and request responsibilities:
(1) Within seven (7) days of PETS confirmation of a McLeodUSA material
infrastructure problem affecting Prodigy, McLeodUSA will provide Prodigy in
writing, a relief date, outlining all dependencies involved (if any) for
providing relief.  (2) McLeodUSA agrees to provide Prodigy a monthly copy of
McLeodUSA's Visual Network Benchmark report and CSV File, (as permitted under
the terms of the McLeodUSA agreement with Visual Networks) and disclose to
Prodigy all access numbers used for the Visual Network Bench Mark test.  (3)
Prodigy will notify McLeodUSA, in a commercially reasonable time frame, of any
authentication, RADIUS or other BackOffice system failures that may compromise
the McLeodUSA authentication network.  (4) If any benchmark or other measurement
device as specified in this agreement is discontinued either by the provider or
by contract termination, the parties shall mutually agree upon a replacement
metric or system.  (5) If any benchmark or other measurement device as specified
in this agreement is discontinued either by the provider or by contract
termination, the parties shall mutually agree upon a replacement metric or
system  (6) In the event the McLeodUSA network performance values for; Call
Failure Rate (CFR) for 24 hour or Evening Hours exceed the allowable performance
levels for an immediately succeeding two consecutive months, Prodigy upon
request and at its election, is entitled to performance credits from McLeodUSA
in the amount equal to appropriate Credit Rate from Credit Rate Table I or
Credit Rate Table II, of the invoiced amount per access number for those access
numbers exceeding the stated performance standard.  All credits are applied
within two invoice

                                       15
<PAGE>

periods. (7) In the event that McLeodUSA's network performance, as measured
against monthly Inverse Benchmark data, is below the following reported industry
average(s) for the number of months indicated below in any of the following
categories Prodigy, at its election, will be entitled to credits from McLeodUSA
as follows:

<TABLE>
<CAPTION>

-----------------------------------------------------------------------------------------------------------
     Category                       Prodigy Does Not Exceed          # of Consecutive     Monthly Invoice
                                    10% of the Forecast for               Months            Credit For
                                         Failed Cities?                                     Each Month
-----------------------------------------------------------------------------------------------------------
<S>                                <C>                                   <C>                 <C>
24 Hour Call Failure Rate                     Yes                             2                  2%
-----------------------------------------------------------------------------------------------------------
Evening-Hour Call Failure Rate                Yes                             2                  2%
-----------------------------------------------------------------------------------------------------------
Modem Connect                                 N/A                             3                 .5%
-----------------------------------------------------------------------------------------------------------
Average Download Time                         N/A                             3                 .5%
-----------------------------------------------------------------------------------------------------------
Average Web Throughput                        N/A                             3                 .5%
-----------------------------------------------------------------------------------------------------------
Business-Hour Call Failure Rate               Yes                             2                 .5%
-----------------------------------------------------------------------------------------------------------
</TABLE>

Notwithstanding the above, the maximum total credit under this Section 24.2(c)
for any given month shall not exceed two percent (2%).  In the event a credit
applies, it applies for each consecutive month and each month thereafter until
McLeodUSA meets or surpasses the applicable industry average category for two
consecutive months.

24.3  McLeodUSA - Other Responsibilities.    McLeodUSA will:
----  -----------------------------------

(a) provide Prodigy with a number for Prodigy's operations group or customer
service group to contact McLeodUSA help desk support, which shall be available
twenty-four (24) hours a day, seven (7) days a week, and staffed adequately to
answer the phone for all Services inquiries within sixty (60) seconds;

(b) use Prodigy's PETS trouble ticketing system in McLeodUSA efforts to resolve
Services Inquiries;

(c) provide Prodigy with a monthly report detailing the status of network
upgrades and expansions within ten days of the end of the immediately preceding
month;

(d) maintain the components, programs, equipment and materials McLeodUSA
provides under this Agreement;

(e) provide Prodigy with read only terminal access to McLeodUSA network
management system so Prodigy can verify operational status of all network modems
and components;

(f) by November 30, 2001,  provide Prodigy:  (1) Enhanced Prodigy NOC to
McLeodUSA NOC communications by providing immediate detection alerts of the
following:  (i) Failure of backbone circuits, (ii) POP failure, (iii) Dial Node
Failure, and

                                       16
<PAGE>

(iv) Peering Point Failure; and (2) within thirty (30) days of completion of the
"real time" alert communication tools above, McLeodUSA will provide Prodigy a
linked tool that will communicate to Prodigy an accurate list of NPA/NXX's
affected by the major failures listed above;

(g) provide Prodigy statistical utilization metrics for McLeodUSA dial access
network that is directly associated with providing dial access to Prodigy users.
These metrics include:  (1) modem ports available to Prodigy End Users; (2)
modem ports utilized by Prodigy End Users; and (3) length of time each port is
utilized;

(h) provide Prodigy with Time Delay statistical data by September 1, 2001.

(i) provide Prodigy with a hard copy map of McLeod's POPs and supporting
infrastructure on a quarterly basis.

(j) participate in formal quarterly meetings, at mutually agreeable dates, times
and locations to discuss the "state of the business" (e.g., performance and
build out), submit proposed agenda items one (1) week prior to the meeting.

(k) provide Prodigy by October 30, 2001 exclusive dedicated dial access numbers
for all POPs listed on Schedule 25.1 or as the Schedule is amended from time to
time;

(l) within 7 days of PETS confirmation of a McLeodUSA material infrastructure
problem affecting Prodigy,  provide Prodigy in writing, a relief date, outlining
all dependencies involved (if any) for providing relief;

(m) provide Prodigy a monthly copy of their Visual Network Benchmark report and
CSV File, (as permitted under the terms of McLeodUSA's agreement with Visual
Networks) and disclose to Prodigy all access numbers used for the Visual Network
Bench Mark test.  If the information is not available under McLeodUSA's
agreement with Visual Networks, McLeodUSA agrees to negotiate with Visual
Networks to obtain access for Prodigy;

(n) make commercially reasonable efforts to notify Prodigy of unscheduled
outages in any portion of the dial network that directly affects Prodigy
Internet customer's ability to login (authenticate) to a POP or the ability to
navigate the Internet;

(o) continue to provide Prodigy a current escalation list, process document and
timing commitments for restoration of unscheduled outage situations on a timely
basis and depending on the assigned severity level of an outage, the appropriate
level of McLeodUSA operational management personnel will engage with the
appropriate level of Prodigy management on current impact and resolution of the
unplanned outage(s);

(p) make commercially reasonable efforts to repair unscheduled outages as soon
as possible to minimize the impact on the Prodigy Internet customers.  Based on
the escalation process (referenced above), McLeodUSA will keep Prodigy informed
as to the current status of the unscheduled outage at set intervals;

(q) notify Prodigy's data NOC of regularly scheduled outages which directly
effect Prodigy Internet customers ability to login (authenticate) to a POP or
the ability to navigate `the Internet' not less than five (5) days in advance.
All Scheduled Maintenance will be performed within the daily rolling time zone
maintenance window (between 2 am and 5 am local time) unless extenuating
circumstances arise which require McLeodUSA to take the necessary and prudent
steps to maintain the integrity of the dial-access and transport network on
which Prodigy traffic is carried;

(r) As a part of the escalation process and notification for Prodigy, McLeodUSA
will provide 24 x 7 access for two (2) Prodigy employees to the McLeodUSA Data
NOC. McLeodUSA will provide two (2) fully equipped computer workstations
complete with

                                       17
<PAGE>

access to the Internet, PETS, and voice communications capability and training
in McLeodUSA NOC procedures for four (4) employees per year free of charge.
McLeodUSA operations staff and Prodigy operations staff will jointly establish
policies, standards and interface agreements to guide the interaction of Prodigy
personnel with McLeodUSA NOC personnel. This interface arrangement will include
specific guidelines governing the support and response time Prodigy should
expect to receive from McLeodUSA NOC operations. Each Prodigy representative
shall be subject to strict confidentiality and shall not disclose any
information, data, conversations or observations related to any McLeodUSA
customers, practices, policies, procedures, network topology or ongoing
restoration efforts. Each Prodigy representative will execute any applicable
confidentiality agreement requested by McLeodUSA with respect to the obligation
of confidentiality; and

(s) McLeodUSA and Prodigy agree to disclose their respective Visual Network
Benchmark access number list two days prior to the start of the monthly test
period.

24.4 Prodigy - Other Responsibilities.    Prodigy will:  (a) notify McLeodUSA,
---- ---------------------------------
in a commercially reasonable time frame, of any authentication, RADIUS or other
BackOffice system failures that may compromise the McLeodUSA authentication
network; (b) participate in formal quarterly meetings, at mutually agreeable
dates, times and locations to discuss the "state of the business" (e.g.,
performance and build out), submit proposed agenda items one (1) week prior to
the meeting; and (c) be responsible for supporting its End Users directly
through its help desk. Prodigy's operations group or customer service group will
contact the McLeodUSA help desk in regard to any reported problems with the
Service being provided by McLeodUSA.

25.  Charges.
---  --------

25.1.  Monthly Usage Charges.
-----  ----------------------

(a) With respect to monthly recurring usage, Prodigy agrees to pay McLeodUSA
based on:  (1) the greater of the total minimum monthly charge ($3.5M or as it
is amended  from time to time), or (2) the total number of monthly connect hours
of your End Users using the Service times the applicable rate per hour per city
as identified on attached Schedule 25.1; and (3) a fixed monthly network access
fee of $1M.  Regardless of any other provision in this Agreement, the total
charges that Prodigy pays to McLeodUSA per month will not be less than $4.5M (or
as it is amended from time to time).  Prodigy may purchase Services from
McLeodUSA for cities not identified on Schedule 25.1 for those cities and at the
rates shown on Schedule 25.2 and such purchase(s) will be included in
determining whether Prodigy has satisfied its minimum commitment under this
Section.

(b) When a decision has been mutually agreed to in writing that a city (POP or
group of POPs) is to be eliminated or added to the list of POPs on Schedule 25.1
and Schedule 25.2 or any other POPs used by McLeodUSA as of the Effective Date,
the Parties agree that the minimum commitment as outlined in Schedule 25.1, and
the $4.5M monthly payment as stated in this Section will be modified by the
amount of the monthly minimum commitment times the then current hourly rate for
that city (POP or group of POPs).

                                       18
<PAGE>

(c) For purposes of determining connect hours, the sequence of a call is as
follows:  dial port goes off hook, modem synchronization, protocol management,
call routed, Prodigy authentication, session live while user performing tasks,
user initiates end of session or the session otherwise ends, eventually
resulting in modem off-line and session termination (carrier dropped).
McLeodUSA will aggregate the total time of all calls, rounded up by city to the
nearest hour.  The length of each individual call will be calculated from the
time the port goes off hook to session end (modem off-line), rounded up to the
nearest second.

(d) In the event that the connect hours for any city (or POP or group of POPs)
in any month is less than the minimum monthly hours traffic commitment as
defined in Schedule 25.1, or the connect hours are within five thousand (5,000)
hours greater than the minimum monthly hours traffic commitment, McLeodUSA shall
notify Prodigy within five (5) business days prior to the end of any month of
that fact.

(e) All pricing for dial access covers speeds up to v.92 capability.  All
pricing of higher speed Services is subject to negotiation and agreement between
the parties.

25.2.  Reduction in Charges.    McLeodUSA represents that it will throughout the
-----  ---------------------
term of this Agreement vigorously pursue reductions in the per city charges
identified on Schedule 25.1 as a result of anticipated cost savings by
McLeodUSA.  To the extent that McLeodUSA realizes incremental cost savings
(defined as those that may accrue as a result of McLeodUSA becoming a CLEC,
installation of new equipment, removal of PRIs, installation of IMT trunks,
etc.) during the term of this Agreement, McLeodUSA will extend fifty percent
(50%) of the cost savings to Prodigy in the form of reduced per city charges on
the beginning of the seventh month following the reduction in costs to
McLeodUSA.  McLeodUSA further agrees to provide Prodigy this costing information
every six months for planning purposes with the first report due on January 1,
2002 and then by specific POP as cost reductions are realized.  McLeodUSA may
reduce any per city rate at any time to remain competitive with the prices of
other network providers.  So long as Prodigy meets the minimum traffic
commitment of Section 25.1 or pays the minimum monthly charge, Prodigy shall be
free to use other network providers for any location that Prodigy provides its
service and/or in any city identified on Schedules 25.1 and 25.2 as may be
amended from time to time.

26.  Forecasts.    (a) Prodigy shall provide McLeodUSA with a rolling four month
     ----------
forecast by the fifth (5th) of each month on access numbers that McLeodUSA
provides complete RADIUS information including DNIS information where provided
to McLeodUSA.  The forecast will provide, to the extent it deviates from the
prior forecast:  (1) Hours of traffic expected for each Prodigy dial access
number; (2) Forecasted time of peak busy hour per day per access number; (3)
Distribution of traffic by hour of day across all sites; and (4) Average session
length across all sites.

(b) McLeodUSA shall use this information to perform capacity planning for the
services provided under this Agreement. Prodigy understands and agrees that
McLeodUSA will utilize the forecast information to increase or decrease the dial
access capacity in each city where Prodigy forecasts hourly usage.  Further,
Prodigy understands and agrees that Prodigy must maintain at least the minimum
hourly traffic level per city specified in Schedule 25.1.  If the actual usage
level in any city is below the minimum, Prodigy shall

                                       19
<PAGE>

be subject to the specified minimum charges per city as provided in Section 25.
The parties further acknowledge and agree that McLeodUSA may make network
related financial commitments based upon Prodigy's forecasts, e.g. purchasing
additional circuits. If the usage is not within ten percent (10%) of Prodigy's
forecast within two (2) months of McLeodUSA adding the additional capacity,
McLeodUSA retains the right to modify the city traffic minimum requirement. This
per city minimum is subject to negotiation and revision between the Parties.

27.  Changes and Default.
---  --------------------

27.1 Undesirable Conditions.  (a) If any of the following undesirable events
---- -----------------------
occurs for two consecutive months or four months out of a twelve-month period,
Prodigy may terminate this Agreement upon forty-five (45) days written notice
("Notice of Termination"):  (1) Overall 24-Hour Call Failure Rate of all access
numbers is greater than fifteen percent (15%); (2) Overall Evening Hour Call
Failure Rate of all access numbers is greater than twenty (20%); (3) Overall 24-
Hour Latency of all access numbers is greater than five hundred (500)
milliseconds; (4) Overall Evening Hour Latency of all access numbers is greater
than seven hundred (700) milliseconds.

(b) If Prodigy desires to terminate this Agreement because of any of the
foregoing undesirable conditions, it must give McLeodUSA a Notice of Termination
within thirty (30) days of receiving the monthly report that gives rise to your
right of termination.  If Prodigy does not exercise its right of termination
within such thirty (30) day period and in the next month the applicable
undesirable condition no longer exists, then Prodigy waives any right of
termination for the applicable time period and this Agreement shall remain in
full force and effect.

(c) Upon Notice of Termination, McLeodUSA shall provide reasonable transition
assistance to you, for a period of up to six months, and no termination
adjustment charge or service level credits shall apply, nor shall charges
specified in Section 25.1(a) apply after the effective date of termination.
Upon termination of the Agreement and after all outstanding amounts owed to
McLeodUSA are paid by Prodigy, McLeodUSA will have ninety (90) days in which to
pay Prodigy any and all credits owed to Prodigy.

27.2.  System Wide Failure.  If fifty (50%) of the POP sites are failing to
-----  --------------------
provide access or Services for forty-eight (48) consecutive hours, then Prodigy
has the right to enter the McLeodUSA premises to assist McLeodUSA in operating
its network assets and direction of its employees, as is necessary to cure such
failure. McLeodUSA shall reimburse Prodigy for any reasonable expense Prodigy
incurs in doing so. McLeodUSA will cooperate with Prodigy's efforts in restoring
service to the network. Prodigy shall also have the right to terminate in
accordance with the termination provisions of Section 27.1. Upon termination of
the Agreement and after all outstanding amounts owed to McLeodUSA are paid by
Prodigy, McLeodUSA will have ninety (90) days in which to pay Prodigy any and
all credits owed to Prodigy.

27.3.  Financial Related Defaults.  (a) Event of Default.  The occurrence of
-----  ---------------------------      -----------------
any of the following events shall constitute an Event of Default:  (1) The
failure of McLeodUSA to perform any of its obligations and covenants under
Section 14; (2) If

                                       20
<PAGE>

Prodigy, in good faith, after reviewing any document or report required to be
delivered under Section 14, believes that there has been a material and adverse
change in business operations and conditions of McLeodUSA, financial or
otherwise, which in Prodigy's reasonable opinion will have a materially adverse
effect upon the operations, business, property, assets, financial condition or
credit of us or Prodigy; (3) If McLeodUSA is acquired, merges with or sells all
of its assets to AT&T, MCI WorldCom, AOL/Time Warner, Earthlink, Sprint or
Microsoft, or any of the affiliates or successors of these entities; or (4) If
McLeodUSA violates any of the Agreement's confidentiality provisions where
McLeodUSA has used Prodigy's customer use patterns to compete or to assist
others to compete against Prodigy.

(b) Remedies.  Upon the occurrence of an Event of Default in this Section,
    ---------
Prodigy shall have the right to terminate this Agreement upon ninety (90) days
written notice.  Upon termination of the Agreement and after all outstanding
amounts owed to McLeodUSA are paid by Prodigy, McLeodUSA will have ninety (90)
days in which to pay Prodigy any and all credits owed to Prodigy.

27.4.  Default (other than for Sections 27.1, 27.2 or 27.3).  (a) In the event
-----  -----------------------------------------------------
that either Party materially defaults in the performance of any of its duties or
obligations under this Agreement (other than Prodigy's failure to make timely
payments due to McLeodUSA) and does not substantially cure such default within
sixty (60) days after being given written notice specifying the default, then
the party not in default may, by giving written notice to the defaulting party,
terminate this Agreement ("Termination for Cause").

(b) In the event Prodigy does not make any payment of the non-disputed charges
due to McLeodUSA by the invoice date, McLeodUSA may terminate this Agreement
upon forty-five (45) days written notice of such default, provided that
McLeodUSA does not receive payment in full for such overdue payment within the
45-day time period.  In the event that Prodigy does not make any other payment
due to McLeodUSA within thirty (30) days of the invoice date, and such failure
is not remedied within sixty (60) days after written notice of nonpayment ("Cure
Period") then McLeodUSA may terminate this Agreement upon the expiration of the
Cure Period.

(c) In the event that Prodigy is in default (for reasons other than failure to
make timely payments due to McLeodUSA) and McLeodUSA elects to terminate this
Agreement, Prodigy may request an extension of this Agreement of up to six (6)
months as a transition period, provided that McLeodUSA, in its discretion,
agrees to provide such an extension.

(d) In the event that Prodigy terminates this Agreement because McLeodUSA is in
material default, then McLeodUSA will provide reasonable transition assistance
to Prodigy, for a period of up to six (6) months.  Upon termination of the
Agreement and after all outstanding amounts owed to McLeodUSA are paid by
Prodigy, McLeodUSA will have ninety (90) days in which to pay Prodigy any and
all credits owed to Prodigy.

28.  Other Terms.    (a) Prodigy is not allowed to test or repair the McLeodUSA
---  ------------
dial network, except as provided in Section 27.2, and except to send Prodigy's
own sample pings similar to that described in Section 27.3.

                                       21
<PAGE>

(b) The Parties agree to seek to bids for the OC-N connections to Yorktown
Heights as soon as is commercially reasonable and at a price that is mutually
acceptable.  The Parties agree to equally share the cost of such OC-N
facilities.  Until such bid is accepted by the Parties, the terms of the May 3,
2000 letter agreement for such facilities will govern.

29.  Auditing Procedures    (a) McLeodUSA shall maintain true and accurate
---  -------------------
accounting records, in accordance with sound accounting practices, to support
the dial connect charges payable by Prodigy.  McLeodUSA shall, upon thirty (30)
days' prior written request, during normal business hours, but not more
frequently than once each calendar quarter, provide access to its records,
associated only with the provision of the Service for the immediately preceding
one-year period, to an independent accounting firm or Prodigy internal auditors
chosen and compensated by Prodigy for the purposes of auditing the accuracy of
the calculation of the dial connect charges.  The accounting firm or internal
auditors selected shall: be required to sign an agreement with protecting
confidential information, perform such audit on our premises, and such other
locations reasonably necessary to conduct a proper audit, comply with security
procedures, and be authorized by McLeodUSA to report only the results of such
audit and provide McLeodUSA with a copy of the report.

(b) In the event that the audit shows that Prodigy owes money to McLeodUSA,
McLeodUSA will invoice Prodigy for such amount within the next two monthly
billing cycles.

(c) In the event that the audit shows a credit due to Prodigy, McLeodUSA will
process such credit including the cost of the audit (but such costs shall not
exceed the credit), excluding travel and per diem charges, plus interest at the
prime rate on the entire amount until paid in full within the next two monthly
billing cycles, provided that McLeodUSA does not disagree with the audit report.
If McLeodUSA disagrees with the audit report, it may select an independent
accounting firm, compensated by it, to perform an audit on the same information
provided to the firm selected by Prodigy.  McLeodUSA shall provide Prodigy a
copy of the report.  In the even that the audit reports disagree on the credit
due to Prodigy, the Parties will resolve the dispute in accordance with Section
31.

30.  Preferred Provider.    (a) McLeodUSA shall be Prodigy's preferred provider
---  -------------------
of dial network access Services except for Prodigy's Agreements with SBC and
pre-existing agreements with other providers. Prodigy shall be free to make
agreements with third parties for Services subject to Prodigy's obligations to
comply with the terms of this Agreement, provided Prodigy shall not seek or
accept any bids for dial network access Services to replace McLeodUSA Services
in their totality (except for replacement of Services by services provided by
SBC). However, Prodigy is free to seek or accept bids for Services for those
cities (or POPs or groups of POPs) that have been eliminated as result of an
agreement between the Parties.

(b) Prodigy shall not offer other services that would result in a material
increase in costs to McLeodUSA, unless the Parties agree on the amount of
increased revenues which will bear a reasonable relationship to such increase in
our costs; provided that, if the Parties cannot agree on the amount of such
increased revenues, the McLeodUSA shall have no obligation to provide our
Services required for such other services.

                                       22
<PAGE>

31.  Alternative Dispute Resolution.    In the event of any dispute or
---  -------------------------------
controversy arising out of or relating to this Agreement, the Parties agree to
exercise their reasonable efforts to resolve the dispute as soon as possible.
The Parties shall without delay continue to perform their respective obligations
under this Agreement, which are not affected by the dispute. To invoke the
dispute resolution process set forth in this paragraph, the invoking party shall
give to the other party written notice of its decision to do so, including a
description of the issues subject to the dispute and a proposed resolution.

(b) Designated representatives of both Parties shall attempt to resolve the
dispute within five (5) working days after such notice.  If those designated
representatives cannot resolve the dispute, the Parties shall meet at Prodigy's
principal place of business or other location as jointly agreed by the Parties
and describe the dispute and their respective proposals for resolution to the
Chief Executive Officers of McLeodUSA and Prodigy, who shall act in good faith
to resolve the dispute.  If the dispute is not resolved within ten (10) calendar
days after such a meeting, the Parties may pursue any remedy available at law or
equity.

(c) Notwithstanding the above, the parties may seek injunctive relief or other
equitable remedies when irreparable injury will occur and no adequate remedy at
law exists.

32.  Publicity.    Each Party will (a) consult with the other party before
---  ----------
issuing any public statement with respect to this Agreement, and (b) give the
other Party a reasonable opportunity to review and comment upon any such
proposed public statement and receive written consent before it is released.

33.  Amendment.    No provision of this Agreement may be modified, waived or
---  ----------
discharged unless such waiver, modification or discharge is agreed to in writing
and signed by the Parties.

34.  Counterparts.    This Agreement may be executed in two or more
---  -------------
counterparts, each of which shall be deemed to be an original, but all such
counterparts shall together constitute one.

35.  Entire Agreement.    This Agreement, including any Schedules, Exhibits A, B
---  -----------------
and C, which is incorporated by reference, constitutes the entire agreement and
understanding between the parties.  Any amendments to this Agreement must be in
writing and executed by both parties.

                                       23
<PAGE>

IN WITNESS WHEREOF, the parties hereto have executed this Agreement on the date
indicated below.

PRODIGY COMMUNICATIONS                  MCLEODUSAUSA
LIMITED PARTNERSHIP                     INFORMATION SERVICES, INC.


By:  /s/ Paul Roth                      By:/s/ Roy A. Wilkens
     -------------                         ------------------

Name:  Paul Roth                        Name:  Roy A. Wilkens

Title: President & CEO                  Title: CEO Networks

Date:  August 1, 2001                   Date:  August 1, 2001

                                       24