<PAGE>

                                                                   Exhibit 10.15

                            STOCKHOLDERS' AGREEMENT
                            -----------------------

     THIS STOCKHOLDERS' AGREEMENT (this "Agreement"), made as of this 9/th/ day
of September, 1999, by and among PaeTec Corp., a Delaware corporation (the
"Corporation"), Alliance Cabletel Holdings, L.P., a Delaware limited partnership
("Alliance"), Kline Hawkes California SBIC, L.P. ("Kline Hawkes"), The Union
Labor Life Insurance Company Separate Account P ("ULLICO"), the individuals
and/or entities listed on Schedule A hereto (together with Alliance, Kline
                          ----------
Hawkes and ULLICO, the "CCS Group Stockholders"), Arunas A. Chesonis ("Mr.
Chesonis"), Christopher Edgecomb, Trustee of the Christopher E. Edgecomb Living
Trust dated April 25, 1998 ("Mr. Edgecomb") and Jeffrey Sudikoff ("Mr.
Sudikoff"; and together with Mr. Chesonis and Mr. Edgecomb, the "Majority
Stockholders").  The CCS Group Stockholders and the Majority Stockholders are
hereinafter sometimes collectively referred to as the "Stockholders" and
individually as a "Stockholder".

                                    RECITALS
                                    --------

     WHEREAS, the Corporation is party to an Agreement and Plan of
Reorganization (the "Merger Agreement") dated as of June 4, 1999, as amended,
with PaeTec Merger Corp., a Delaware corporation and a wholly-owned subsidiary
of the Corporation (the "Merger Sub"), and Campuslink Communications Systems,
Inc., a Delaware corporation ("Campuslink"), pursuant to which the Merger Sub
will be merged with and into Campuslink, with Campuslink being the surviving
entity (the "Merger").

     WHEREAS, pursuant to subscription agreements, certain of the CCS Group
Stockholders purchased from the Corporation in a private placement an aggregate
of 1,200,000 shares of Class A Common Stock of the Corporation, $0.01 per value
per share ("Class A Common Stock").

     WHEREAS, pursuant to a proposed Common Stock Purchase Agreement (the "PCG
Purchase Agreement") to be entered into between Star Telecommunications, Inc.
("Star") and Pacific Capital Group, Inc. ("PCG"), PCG, who is an Affiliate of
Alliance, may purchase (either on its own behalf or with other purchasers
designated by it, one or more of whom may be CCS Group Stockholders) 2,900,000
shares of Class A Common Stock owned by Star (such shares (upon acquisition by
PCG or its designees) being referred to in this Agreement as the "PCG Shares"),
which PCG shares will not be covered by this Agreement but will (assuming such
contemplated purchase is consummated) be subject to a Stockholders' Agreement
with the Corporation and the Majority Stockholders which is similar to this
Agreement (the "PCG Stockholders' Agreement").

     WHEREAS, upon consummation of the Merger, Campuslink will become a wholly-
owned subsidiary of the Corporation, and each of the CCS Group Stockholders, who
constitute all of the holders of capital stock and warrants to purchase capital
stock of Campuslink, will own that number of shares of Class A Common Stock
and/or that number of options to purchase Class A Common Stock (the "Options")
as set forth opposite each individual's or entity's name on
<PAGE>

Schedule B attached to this Agreement (which numbers include the shares of Class
----------
A Common Stock referred to in the above recital).

     WHEREAS, the Majority Stockholders currently own that number of shares of
Class A Common Stock, and that number of shares of Class B Common Stock of the
Corporation ("Class B Common Stock"), $0.01 par value per share, as set forth
opposite each Majority Stockholder's name on Schedule C attached to this
                                             ----------
Agreement.

     WHEREAS, pursuant to Sections 8.10 and 9.10 of the Merger Agreement, it is
a condition precedent to the obligations of the parties thereunder to consummate
the Merger that the parties enter into this Agreement.

     WHEREAS, the Stockholders believe that it is in the best interests of the
parties hereto (a) to formalize their agreements relating to preemptive and tag-
along rights upon certain transfers of Securities (as defined below); (b) to
formalize their agreements regarding certain voting matters; and (c) to define
certain rights, duties and obligations among the parties hereto.

     NOW, THEREFORE, the Stockholders and the Corporation agree as follows:

     1.   Definitions.
          -----------

          1.1  "Affiliate" shall mean any Person that directly, or indirectly
                ---------
through one or more intermediaries, controls or is controlled by, or is under
common control with, any other Person.

          1.2  "Common Stock" shall mean, collectively, the Class A Common
                ------------
Stock and the Class B Common Stock of the Corporation.

          1.3  "Majority Stockholders' Agreement" shall mean that certain
                --------------------------------
Stockholders' Agreement dated August 13, 1998 between Mr. Chesonis, Mr.
Edgecomb, as Trustee of the Christopher E. Edgecomb Living Trust dated April 25,
1998, and Mr. Sudikoff, as such Stockholders' Agreement is in effect as of the
date hereof.

          1.4  "Permitted Transferee" shall mean the transferee of any
                --------------------
Securities of any Stockholder who is an Affiliate of such Stockholder or the
spouse, lineal descendents (natural or adopted) or parents of such Stockholder
or Affiliate, or (with the prior consent of the Corporation, which consent shall
not be unreasonably withheld or delayed) the respective constituent partners or
participants of such Stockholder or such partners' or participants' direct and
indirect constituent partners, stockholders and Affiliates, or an inter vivos
                                                                  ----- -----
trust for the benefit of any such person.

          1.5  "Person" shall mean any individual, corporation, partnership
                ------
(general or limited), limited liability company, limited liability partnership,
firm, trust, association or other entity.

                                       2
<PAGE>

          1.6  "Securities" shall mean, collectively, all capital stock of the
                ----------
Corporation, all rights to acquire any shares of any capital stock of the
Corporation and all securities convertible into capital stock of the Corporation
(including indebtedness convertible into or exchangeable for shares of capital
stock of the Corporation), together with any and all securities received as
stock splits, dividends on or in substitution for any capital stock of the
Corporation, or in connection with any increase, reduction or reclassification
of the capital stock of the Corporation, or upon any reorganization,
recapitalization, share exchange, exchange offer, merger or consolidation of the
Corporation with any one or more entities in which an entity other than the
Corporation is the surviving entity, or upon the exercise of any option or
warrant to purchase capital stock of the Corporation.

          1.7  "Stock Rights Agreements" shall mean, collectively, (i) the Stock
                -----------------------
Rights Agreements, dated as of July 17, 1998 and as amended as of August 13,
1998 and September 30, 1998, by and among the Corporation, PaeTec
Communications, Inc., Arunas A. Chesonis and each of Joseph D. Ambersley,
John Baron, Bradford M. Bono, Edward J. Butler, Richard E. Ottalagana,
Richard J. Padulo and Daniel J. Venuti; (ii) the Stock Rights Agreement, dated
as of August 13, 1998 and as amended as of September 30, 1998, by and among the
Corporation, PaeTec Communications, Inc., Arunas A. Chesonis and
Timothy J. Bancroft; and (iii) the Stock Rights Agreement, dated as of October
30, 1998, by and among the Corporation, PaeTec Communications, Inc.,
Arunas A. Chesonis and Katherine A. Chapman, each as in effect as of the date of
this Agreement.

          1.8  "Transfer" shall mean any sale, pledge, assignment, encumbrance,
                --------
transfer, hypothecation, gift or other alienation, by operation of law or
otherwise, of any Securities.

     2.   Tag-Along Rights.
          ----------------

          2.1  Right to Transfer.  If, at any time, one or more Majority
               -----------------
Stockholders (which term, for purposes of this Section 2 shall refer to such
Majority Stockholders and/or each of the Permitted Transferees of such Majority
Stockholders) propose to Transfer any Securities to any Person (other than (a) a
Transfer to a Permitted Transferee and (b) the Transfer by Mr. Chesonis of not
more than 25,000 shares of Common Stock pursuant to an option agreement with
James Daleen), such Majority Stockholder (a "Transferring Stockholder") shall
give written notice to each of the CCS Group Stockholders (which term, for
purposes of this Section 2 shall refer to such CCS Group Stockholder and/or each
of the Permitted Transferees of such CCS Group Stockholders) ("Non-Transferring
Stockholders") and the Corporation at least 25 business days prior to the
consummation of the proposed Transfer (the "Tag-Along Notice"). Each Non-
Transferring Stockholder may, upon giving written notice to the Transferring
Stockholder and the Corporation within 15 business days after its receipt of the
Tag-Along Notice (a "Tag-Along Election Notice"), participate in such Transfer
on a pro rata basis, at the same price and upon the same terms and conditions as
     --- ----
are applicable to the Transferring Stockholder in such transaction.  For
purposes of the preceding sentence, each Non-Transferring Stockholder's pro rata
                                                                        --- ----
share shall

                                       3
<PAGE>

be a percentage of the total number of Securities that the purchaser agrees to
purchase, such percentage to be determined by dividing (a) the number of
Securities that such Non-Transferring Stockholder submits for sale pursuant to
Section 2.2, by (b) the number of Securities proposed to be sold by the
Transferring Stockholder plus the total number of Securities that all Non-
Transferring Stockholders submit for sale pursuant to Section 2.2, plus, with
respect to a proposed Transfer by Mr. Chesonis, the total number of Securities
that Mr. Edgecomb and Mr. Sudikoff have the right to Transfer in such
transaction pursuant to Section 3 of the Majority Stockholders' Agreement, plus
the total number of Securities that certain Officers of the Corporation have the
right to Transfer in such transaction pursuant to the Stock Right Agreements.

          2.2  Percentage Participation.  Each Non-Transferring Stockholder may
               ------------------------
submit for sale the same percentage of the holdings of each class of Securities
of the Corporation held by the Non-Transferring Stockholder as the quantity of
the corresponding class of Securities being sold by the Transferring Stockholder
represents of the Transferring Stockholder's total holdings of that class.  For
this purpose, (a) the Class A Common Stock of the Corporation and the Class B
Common Stock of the Corporation shall be deemed one and the same class of
securities and (b) subject to Section 2.3 below, holdings of Common Stock and
holdings of warrants, options (including the Options held by one or more of the
CCS Group Stockholders) or other rights to purchase Common Stock shall be
treated as being identical.

          2.3  Common Stock Equivalents.  If the Transferring Stockholder
               ------------------------
proposes to Transfer Common Stock or warrants, options or other rights to
purchase Common Stock (which Common Stock, warrants, options and rights are
individual and collectively sometimes referred to herein as "Common Stock
Equivalents"), the Non-Transferring Stockholder may sell Common Stock
Equivalents. The per share purchase price paid for Common Stock Equivalents held
by the Non-Transferring Stockholder shall be the per share price paid for the
Common Stock Equivalents being sold by the Transferring Stockholder. In such
case, the per share price paid for Common Stock Equivalents shall be the same
but with an adjustment to take into account the cost, or any difference in cost,
of purchasing Common Stock upon exercise of the warrants, options and
subscription rights.

          2.4  Requirement to Purchase.  If any Non-Transferring Stockholder
               -----------------------
gives a timely Tag-Along Election Notice, the Transferring Stockholder shall
require the purchaser, as a condition precedent to consummating the purchase of
Securities from the Transferring Stockholder, purchase the Securities that the
Non-Transferring Stockholder is entitled to Transfer under this Section 2.
Subject to Section 2.3, such purchase shall be at the same price and upon the
same terms and conditions as are applicable to the sale by the Transferring
Stockholder. The Transferring Stockholder shall not complete its sale to the
purchaser if the purchaser fails to satisfy the condition precedent referred to
in the second preceding sentence.

          2.5  Termination of Tag-Along Rights.  The rights granted to the CCS
               -------------------------------
Group Stockholders pursuant to this Section 2 shall terminate upon the
completion by the Corporation of an initial public offering of its Common Stock
with gross proceeds from such offering of $25

                                       4
<PAGE>

million or greater.

          2.6  No Other Tag-Along Rights.  Except for (i) the rights granted
               -------------------------
to the CCS Group Stockholders under Section 2 of this Agreement, (ii) the co-
sale rights granted to Mr. Edgecomb and Mr. Sudikoff under the Majority
Stockholders' Agreement, (iii) the co-sale rights granted under the Stock Rights
Agreements, and (iv) the tag-along rights to be granted to PCG and its designees
under the PCG Stockholders' Agreement, no Majority Stockholder shall grant tag-
along, co-sale or other rights similar to the rights granted to the CCS Group
Stockholders under this Section 2 (i.e., the right to participate in the
                                   ---
Transfer of Securities in connection with a Transfer of Securities by a Majority
Stockholder) without the prior written consent of CCS Group Stockholders holding
a majority of the shares of Common Stock held by all CCS Group Stockholders on
the applicable date that such Majority Stockholder desires to grant such rights.

     3.   Rights Upon Issuance of Stock by the Corporation.
          ------------------------------------------------

          3.1  Right to Purchase.  Subject to Section 3.3 below, each CCS Group
               -----------------
Stockholder (which term, for purposes of this Section 3 shall refer to (i) each
CCS Group Stockholder, (ii) each of the Permitted Transferees of each CCS Group
Stockholder, and (iii) each third party transferee of Securities from a CCS
Group Stockholder who is entitled to enjoy the rights of such CCS Group
Stockholder hereunder pursuant to Section 8.5 of this Agreement) shall have a
preemptive right (that is, a right to purchase such CCS Group Stockholder's pro
                                                                            ---
rata share of all capital stock of the Corporation on a fully diluted basis
----
assuming the exercise of all outstanding options and warrants to purchase
capital stock of the Corporation, based on such CCS Group Stockholder's actual
and assumed holdings at that date, at the same price and on the same terms and
conditions as those upon which such capital stock is proposed to be sold) to
acquire any shares of any class of capital stock of the Corporation, including
unissued shares, treasury shares or any rights or options to purchase such
capital stock, or any securities convertible into or exchangeable for such
capital stock or any options to purchase such convertible or exchangeable
securities (collectively, "Capital Stock"), authorized by the Board of Directors
of the Corporation for issuance after the date hereof; provided, however, that
                                                       --------  -------
the foregoing provision shall not apply to any such Capital Stock of the
Corporation: (a) issued upon the exercise of the warrants and options listed on
Schedule 3.1 to this Agreement or warrants or options granted or Common Stock
------------
issued by the Company after the date of this Agreement pursuant to the
Corporation's 1998 Incentive Compensation Plan or Agent Bonus Plan each as in
effect on the date hereof; (b) issued in connection with a stock split or
dividend; (c) issued in connection with a merger or consolidation approved
pursuant to Section 5.1(g) of this Agreement; (d) issued upon the exchange,
conversion or exercise of any Securities that are exchangeable for, convertible
into or exercisable for shares of the Corporation's capital stock, the original
issuance of which was authorized in compliance with Section 5.1 of this
Agreement; or (e) issued in connection with an initial public offering of the
Corporation's Common Stock with gross proceeds in excess of $25 million.

          3.2  Procedure.  Prior to any issuance or sale by the Corporation of
               ---------
any shares of Capital Stock subject to the rights described in subsection 3.1
above, the Corporation shall

                                       5
<PAGE>

notify each CCS Group Stockholder, in writing, of its intention to sell or issue
such shares, setting forth in reasonable detail the consideration and other
terms under which it proposes to make such sale or issuance (the "Corporation
Notice"). Within 20 business days after the Corporation Notice, each CCS Group
Stockholder shall notify the Corporation whether such CCS Group Stockholder
elects to purchase such CCS Group Stockholder's pro rata share (or any part
                                                --- ----
thereof) of the shares so offered upon the consideration and other terms set
forth in the Corporation Notice. If, within such 20 business days, a CCS Group
Stockholder shall have notified the Corporation of his or its election to
exercise the right granted pursuant to Section 3.1 above, such CCS Group
Stockholder shall purchase his or its pro rata share (or any part thereof) of
                                      --- ----
the shares, on the consideration and other terms set forth in the Corporation
Notice by the later of (a) the 10/th/ day after delivery of his or its notice to
the Corporation electing to exercise the foregoing right and (b) the closing of
the transaction referred to in the Corporation Notice. If, however, such CCS
Group Stockholder shall not, within 20 business days after the Corporation
Notice, have notified the Corporation that such CCS Group Stockholder elects to
exercise the right granted pursuant to Section 3.1 above with regard to any or
all of the shares subject to the transaction described in the Corporation
Notice, such CCS Group Stockholder shall be deemed to have waived his or its
rights under this Section 3 with respect to any portion of the shares that he or
it shall not have elected to purchase; provided, however, that failure by a CCS
                                       --------  -------
Group Stockholder to exercise or to consummate his or its option to purchase
with respect to one sale or issuance shall not affect the option to purchase
shares under this Section 3 in any subsequent sale or issuance.

          3.3  Termination of Right.  The right to purchase granted to each CCS
               -----------------
Group Stockholder pursuant to this Section 3 shall terminate upon the completion
by the Corporation of an initial public offering of its Common Stock, with gross
proceeds from such offering of $25 million or greater.

     4.   Matters Concerning the Board of Directors.
          -----------------------------------------

          4.1  Director Voting.  So long as Mr. Chesonis owns (whether
               ---------------
beneficially or of record) or otherwise has the right to vote any shares of
Class B Common Stock of the Corporation, Mr. Chesonis shall vote all of his
shares of Common Stock (including the shares of Common Stock owned by others
which he has the right to vote) for the election of (i) that number of nominees
to serve as directors of the Corporation nominated by the CCS Group Stockholders
(which term, for purposes of this Section 4 shall refer to each CCS Group
Stockholder and/or each of the Permitted Transferees of each CCS Group
Stockholder and/or each of the Permitted Transferees of each CCS Group
Stockholder) (the "CCS Group Directors") which shall equal the greater of (a) a
number of members of the Board of Directors of the Corporation by the CCS Board
Percentage and (b) one nominee and (ii) any nominee designated by the CCS Group
Stockholders to fill any vacancy created by the resignation or removal of any
then current CCS Group Director. For

                                       6
<PAGE>

purposes of this Section 4.1, the "CCS Board Percentage" shall be equal to the
total number of shares of Common Stock owned by the CCS Group Stockholders
(excluding any PCG Shares owned by the CCS Group Stockholders) divided by the
total number of issued and outstanding shares of Common Stock of the
Corporation. For purposes of this Section 4.1, nominees to serve as CCS Group
Directors shall be determined by the vote of CCS Group Stockholders holding a
majority of the shares of Common Stock held by all the CCS Group Stockholders on
the applicable date that a nominee is required to be nominated. Other than any
votes cast for the CCS Group Directors (or any directors which PCG becomes
entitled to nominate under the PCG Stockholders' Agreement), the CCS Group
Stockholders shall vote all of their shares of Common Stock for the election of
any director nominees by Mr. Chesonis.

          4.2  Termination.  The provisions set forth in this Section 4 shall
               -----------
terminate on the first to occur of (a) the date that Mr. Chesonis ceases to own,
or otherwise have the right to vote, any shares of Class B Common Stock of the
Corporation and (b) the date that the CCS Group Stockholders (including their
Permitted Transferees) cease to own, on an aggregate basis, at least 5% of the
issued and outstanding shares of Common Stock of the Corporation.

     5.   Approval of Certain Transactions.
          --------------------------------

          5.1  Approval of Major Transactions.  The Corporation shall not, on or
               ------------------------------
after the date hereof, directly or indirectly, authorize or engage in any Major
Transaction (as defined below) without the approval of a majority of the CCS
Group Directors, or, if there are only two CCS Group Directors, then without the
approval of both CCS Group Directors.  The term "Major Transaction" shall
consist of:

          (a)  any acquisitions of assets for consideration in excess of (i) $10
     million in any single transaction or series of relation transactions, or
     (ii) $25 million in the aggregate (which amount shall be increased to $50
     million upon completion by the Corporation of a high yield debt offering
     with gross proceeds of at least $100 million);

          (b)  any leases providing for payment obligations in excess of (i) $5
     million in any single transaction or series of related transactions, or
     (ii) $25 million in aggregate leases at any one time;

          (c)  any disposition, lease, conveyance or transfer of assets with a
     value in excess of $1 million in any single transaction or series of
     related transactions;

          (d)  any encumbrance of the Corporation's (or any subsidiary's) assets
     (other than statutory liens for monies not yet due and purchase money
     security interests not in excess of $1 million in the aggregate in force at
     any one time);

          (e)  any borrowings by the Corporation (or any subsidiary) of $25
     million or greater, in the aggregate, at any one time;

          (f)  any acquisition or sale of securities of another Person with a
     purchase price of $25 million or greater;

                                       7
<PAGE>

          (g)  any merger or consolidation of the Corporation or any of its
     subsidiaries with or into any other Person or any reclassification or other
     exchange of any stock, provided that this paragraph shall not involve any
     transaction in which the Corporation or its subsidiary is the surviving
     entity and which involves aggregate consideration to the equity owners of
     the other party (or parties) of not more than $10 million.

          (h)  any issuance, or any agreement to issue, by the Corporation of
     any Securities of the Corporation other than pursuant to the Corporation's
     1998 Incentive Compensation Plan or Agent Bonus Plan, as each such Plan is
     in effect on the date hereof or pursuant to the options issued to Clinton
     Walker, Lodwrick Cook and Stephen Mayo on the date hereof in connection
     with the Merger;

          (i)  any purchase, redemption or other acquisition for value (or any
     payment into or setting aside as a sinking fund for such purpose) and any
     Securities of the Corporation;

          (j)  the entering into of any contract, agreement or arrangement which
     is outside the ordinary course of the Corporation's business (it being
     understood that any agreement relating to the resale of energy is outside
     the ordinary course of the Corporation's business, and agreements for
     telecommunications services, including content over digital subscriber
     lines, Internet services or other related services are generally within the
     ordinary course of business) or which is with any officer, director or
     stockholder of the Corporation or any affiliate of such officer, directors
     or stockholder;

          (k)  any amendment to the charter documents or bylaws of the
     Corporation; and

          (l)  any transaction which would materially change the nature of the
     Corporation's business.

          5.2  Termination.  The provisions of this Section 5 shall terminate on
               -----------
the first to occur of (a) the date of the completion of the Corporation of an
initial public offering of its Common Stock, with gross proceeds from such
offering of $25 million or greater and (b) the date that the CCS Group
Stockholders (including their Permitted Transferees) cease to own, on an
aggregate basis, at least 5% of the issued and outstanding shares of Common
Stock of the Corporation.

     6.   Legend on Securities; Additional Securities.
          -------------------------------------------

          6.1  Legend.  Each certificate or instrument representing, and any
               ------
future certificate or instrument evidencing ownership of, the Securities that
are subject to this Agreement  will be conspicuously imprinted with the
following legends:

                                       8
<PAGE>

     "THE SECURITIES REPRESENTED HEREBY HAVE NOT BEEN REGISTERED UNDER
     THE SECURITIES ACT OF 1933, AS AMENDED, OR UNDER ANY STATE
     SECURITIES LAWS. THE SECURITIES MAY NOT BE SOLD OR TRANSFERRED IN
     THE ABSENCE OF SUCH REGISTRATION OR AN EXEMPTION THEREFROM UNDER
     SAID ACT AND APPLICABLE STATE LAWS."

     "IN ADDITION, SUCH SECURITIES ARE SUBJECT TO THE TERMS AND
     CONDITIONS OF A STOCKHOLDERS' AGREEMENT DATED AS OF SEPTEMBER 9,
     1999 BETWEEN PAETEC CORP., AND CERTAIN STOCKHOLDERS OF PAETEC
     CORP. THE VOTING AND SALE, TRANSFER OR OTHER DISPOSITION OF THESE
     SECURITIES IS SUBJECT TO THE TERMS OF SUCH STOCKHOLDERS'
     AGREEMENT AND SUCH SECURITIES WILL BE TRANSFERRED ONLY UPON PROOF
     OF COMPLIANCE THEREWITH."

The legend in respect of this Agreement shall not be removed from the Securities
so long as this Agreement remains in effect.  The legend in respect of the
compliance with applicable federal or state securities laws shall be removed if
an opinion of counsel reasonably satisfactory to the Corporation and the
Corporations' counsel is provided to the Corporation that such legend is not
required in order to establish compliance with any provisions of the Securities
Act or applicable state securities laws.

          6.2  Additional Securities.  If the Corporation distributes any of its
               ---------------------
shares of Common Stock or other Securities to any of the Stockholders as a
dividend upon any of the Securities then outstanding or issues any of its
Securities to any of the Stockholders in lieu of, or in exchange for, or in
addition to Securities then outstanding, or any Stockholder acquires or obtains
any additional Securities, then, and in any of such events, any such Securities
distributed or issued or acquired or obtained by any Stockholder will be deemed
to be "Securities" under this Agreement and will be subject to the terms of this
Agreement.

     7.   Injunctive Relief.  Each Stockholder and the Corporation acknowledges
          -----------------
and agrees that the terms, covenants and obligations of this Agreement relate to
special, unique and extraordinary matters and that a violation of any of the
terms, covenants or obligations of this Agreement will cause the Corporation and
each Stockholder irreparable injury in an amount which would be impossible to
estimate or determine and for which adequate compensation could not be
fashioned.  Therefore, each Stockholder and the Corporation agrees that the
Corporation and/or the other Stockholders (as applicable) will be entitled to an
injunction, restraining order or other equitable relief as a matter of course,
and without the necessity of proving irreparable harm or the inadequacy of a
legal remedy or posting a bond, from any court of competent jurisdiction,
restraining the applicable Stockholders or the corporation and any other
person(s) as the court may order from committing any violation or threatened
violation of the terms, covenants or obligations in this Agreement.  The
Corporation's and each Stockholder's rights and remedies under this Section 7
are cumulative and are in addition to any other rights and remedies that the

                                       9
<PAGE>

Corporation or any Stockholder may have under this Agreement or any other
agreement or at law or in equity.

     8.   Miscellaneous.
          -------------

          8.1  Continuing Force; Remedies Cumulative.  The provisions contained
               -------------------------------------
in this Agreement will survive and remain in full force and effect after
execution of this Agreement.  The  remedies contained in this Agreement will
survive and remain in full force and effect after the termination of this
Agreement.  The rights and remedies provided for in this Agreement are
cumulative and will be in addition to rights and remedies otherwise available to
the parties under any other agreement or applicable law.

          8.2  Amendment.  This Agreement may only be amended by a written
               ---------
agreement signed by each of the Majority Stockholders and by the CCS Group
Stockholders holding at least 75% of the Common Stock owned by all of the CCS
Group Stockholders covered by this Agreement on a fully diluted basis (assuming
the exercise of all warrants or options to purchase Common Stock and the
conversion of all Securities convertible into shares of Common Stock held by
such CCS Group Stockholder) at the time of the proposed amendment; provided,
                                                                   --------
however, that no amendment may adversely affect the rights of the CCS Group
-------
Stockholders under Sections 2 and 3 of this Agreement without the consent of
each CCS Group Stockholder.

          8.3  Waiver.  No waiver of any Section of provision of this Agreement
               ------
will be valid unless in a writing signed by the party to be charged and only to
the extent set forth in that writing.  Unless such a writing expressly provides
otherwise, any waiving by any party of any Section or provision of this
Agreement will not operate or be construed as a waiver of any subsequent breach
of this Agreement or constitute a course of conduct which may be relied upon to
justify any subsequent breach of this Agreement.

          8.4  Notices.  All notices, demands and other communications called
               -------
for or required by this Agreement shall be in writing and shall be addressed to
the parties at their respective addresses  stated below or to such other address
as a party may subsequently designate by written notice to the other parties.
Communications hereunder shall be deemed to have been received (i) upon delivery
in person, (ii) five days after mailing it by U.S. certified mail, return
receipt requested and postage prepaid, (iii) the first business day after
depositing it with a commercial overnight carrier which provides written
verification of delivery, or (iv) the day of transmission if sent before 2:00
p.m. recipient's time by facsimile transmission (with confirmation of receipt)
provided that a copy of such notice is sent on the same day by U.S. certified
mail, return receipt requested and postage prepaid, with an indication that the
original was sent by facsimile and the date of its transmittal.

          If to the Corporation to:

                    PaeTec Corp.

                                       10
<PAGE>

                    290 Woodcliff Drive
                    Fairport, New York
                    Attention: President and Chief Executive Officer
                    Telecopier: (716) 340-2547

          with a copy to:

                    Bond, Schoeneck & King, LLP
                    One Lincoln Center
                    Syracuse, New York 13202
                    Attention: Wallace J. McDonald, Esq.
                    Facsimile: (315) 422-3598

or at such other address and to the attention of such other person as the
Corporation may designate by written notice to the CCS Group Stockholders.
Notices to any CCS Group Stockholder shall be addressed to such stockholder at
the most current address set forth in the Corporation's books and records with a
copy to:

                    Kirkland & Ellis
                    200 East Randolph Drive
                    Chicago, IL 60601
                    Attention: David A. Breach, Esq.
                    Facsimile Number: (312) 861-2200

or at such other address and to the attention of such other person as the
applicable CCS Group Stockholder may designate by written notice to the
Corporation. Notices to the Majority Stockholders shall be addressed to:

                    Arunas A. Chesonis
                    c/o PaeTec Corp.
                    290 Woodcliff Drive
                    Fairport, New York 14450
                    Facsimile: (716) 340-2547

                    Christopher Edgecomb, Trustee
                      of the Christopher E. Edgecomb Living Trust
                      dated April 25, 1998
                    c/o STAR Telecommunications, Inc.
                    223 East De La Guerra
                    Santa Barbara, California 93101
                    Facsimile: (805) 884-1137

                    Jeffrey Sudikoff
                    P.O. Box 491669

                                       11
<PAGE>

                    Los Angeles, California 90049
                    Facsimile: (310) 382-3376

or at such other address and to the attention of such other person as the
Majority Stockholders may designate by written notice to the Corporation.

          8.5  Binding Effect and Assignment.  This Agreement, and the rights
               -----------------------------
and duties under it, will be binding upon and inure to the benefit of (a) the
Corporation, its successors and assigns, and (b) each Stockholder, its
successors and assigns.  No Stockholder may assign its rights under this
Agreement or delegate its duties hereunder unless such Stockholder both assigns
its rights and delegates its duties hereunder and such assignment and delegation
is made in connection with a Transfer of Securities by a CCS Group Stockholder
to a third party who is not a Permitted Transferee, such transferee shall only
enjoy the rights of a CCS Group Stockholder pursuant to Section 3 of this
Agreement and not the rights of a CCS Group Stockholder pursuant to Sections 2,
4 and 5 of this Agreement.  In connection with any Transfer to any Permitted
Transferee, or to any third party as contemplated by the preceding sentence of
this Section 8.5, the transferring Stockholder shall obtain from such transferee
an agreement in writing, in a form reasonably satisfactory to the applicable
parties, to be bound by this Agreement and that Securities transferred shall
remain subject to the terms of this Agreement.

          8.6  Governing Law.  This Agreement will be governed by, and construed
               -------------
and enforced in accordance with, the laws of the State of New York, except that
if any provision of this Agreement or any part of any such provision would be
illegal, invalid or enforceable under such laws in connection with a suit or
proceeding validity instituted in another jurisdiction, then the laws of such
other jurisdiction will govern insofar as is necessary to sustain the legality,
validity or Enforceability of such provision or any part of such provision.

          8.7  Captions.  Captions to the various Sections in this Agreement are
               --------
for the convenience of the parties only and will not affect the meaning or
interpretation of this Agreement.

          8.8  Enforceability and Interpretation.  It is the desire and intent
               ---------------------------------
of the parties to this Agreement that the terms, provisions, conditions,
covenants, representations, warranties, and remedies contained in this Agreement
will be enforceable to the fullest extent permitted by law.  If any term,
provision, condition, covenant, representation, warranty, or remedy of this
Agreement or the application thereof to any person or circumstances will, to any
extent, be construed to be illegal, invalid, or unenforceable, in whole or in
part, then such terms, provisions, condition, covenant, representation,
warranty, or remedy will be construed in a manner so as to permit its
enforceability under the applicable law to the fullest extent permitted by such
law.  In any case, the remaining terms, provisions, conditions, covenants,
representations, warranties, and remedies of this Agreement or the application
thereof to any person or circumstance, except those which have been held
illegal, invalid, or unenforceable, will remain in full force and effect.

          8.9  Counterparts.  This Agreement may be executed in one or more
               ------------

                                       12
<PAGE>

counterparts, each of which will be deemed an original, but together they will
constitute one and the same instrument.

          8.10 Additional Documents.  Each Stockholder agrees to execute any and
               --------------------
all documents, instruments, certificates and communications deeded to be
necessary or desirable by the Corporation to effectuate or reconfirm the
applicability of this Agreement to any and all future transaction affecting the
Corporation, the Securities, or any Stockholder.

          8.11 Cost of Enforcement.  Any party of this Agreement shall pay to
               -------------------
any other party all fees and expenses (including reasonable fees and expenses of
attorneys) incurred by such other party in enforcing its rights under this
Agreement against such party.

                                       13
<PAGE>

     IN WITNESS WHEREOF, the parties hereto have executed and delivered this
Agreement with full force and effect as of the day and year first written above.

                                   THE CORPORATION:

                                   PAETEC CORP.

                                   By: Arunas A. Chesonis
                                      -----------------------------------------

                                      Its: President
                                          -------------------------------------


                                   MAJORITY STOCKHOLDERS:

                                   /s/ Arunas A. Chesonis
                                   --------------------------------------------
                                   Arunas A. Chesonis

                                   CHRISTOPHER E. EDGECOMB
                                   LIVING TRUST, dated April 25, 1998

                                   /s/ Christopher Edgecomb
                                   --------------------------------------------
                                   Christopher Edgecomb, Trustee

                                   /s/ Jeffrey Sudikoff
                                   --------------------------------------------
                                   Jeffrey Sudikoff


                                   CCS GROUP STOCKHOLDERS:

                                   ALLIANCE CABLETEL HOLDINGS, L.P., a Delaware
                                   limited partnership

                                   By: KOCOM COMMUNICATIONS, INC., a
                                       Delaware limited partnership

                                   By: /s/ James A. Kofalt
                                      -----------------------------------------
                                      James A. Kofalt, President


                                       14
<PAGE>

                                   KLINE HAWKES CALIFORNIA SBIC, L.P.

                                   By: [SIGNATURE ILLEGIBLE]
                                      ----------------------------------------

                                      Its: Chairman
                                          ------------------------------------
                                   THE UNION LABOR LIFE INSURANCE COMPANY
                                   SEPARATE ACCOUNT P


                                   By: [SIGNATURE ILLEGIBLE]
                                      ----------------------------------------

                                      Its: VP Investments
                                          ------------------------------------

                                   /s/ Robert I. Schwartz
                                   -------------------------------------------
                                   Robert I. Schwartz

                                   /s/ Kenneth M. Kiraly
                                   -------------------------------------------
                                   Kenneth M. Kiraly

                                   /s/ Susan F. Kiraly
                                   -------------------------------------------
                                   Susan F. Kiraly

                                   /s/ Richard P. Rizzutti
                                   -------------------------------------------
                                   Richard P. Rizzutti

                                   /s/ Bryant Hopper
                                   -------------------------------------------
                                   Bryant Hopper

                                   /s/ Ronald S. Johnson
                                   -------------------------------------------
                                   Ronald S. Johnson

                                   /s/ Lodwrick Cook
                                   -------------------------------------------

                                       15
<PAGE>

                                   Lodwrick Cook

                                   /s/ Peter Cracovaner
                                   -------------------------------------------
                                   Peter Cracovaner

                                   /s/ Richard Cunningham
                                   -------------------------------------------
                                   Richard Cunningham

                                   /s/ Thomas O. FitzGerald
                                   -------------------------------------------
                                   Thomas O. FitzGerald

                                   /s/ Wendy Foliano
                                   -------------------------------------------
                                   Wendy Foliano

                                   /s/ Joseph Golden
                                   -------------------------------------------
                                   Joseph Golden

                                   /s/ Stephen Mayo
                                   -------------------------------------------
                                   Stephen Mayo

                                   /s/ Karen Sancimino
                                   -------------------------------------------
                                   Karen Sancimino

                                   /s/ Clinton Walker
                                   -------------------------------------------
                                   Clinton Walker

                                       16
<PAGE>

                                   SCHEDULE A

Robert I. Schwartz
Kenneth M. and Susan F. Kiraly
Richard P. Rizzuti
Bryant Hopper
Ronald S. Johnson
Lodwrick Cook
Peter Cracovaner
Richard Cunningham
Thomas O. FitzGerald
Wendy Foliano
Joseph Golden
Stephen Mayo
Karen Sancimino
Clinton Walker

                                       17
<PAGE>

                                   SCHEDULE B

                                           Common Stock          Options
     Holder                               (Number of Shares) (Number of Shares)
     ------                               ------------------ -----------------

Alliance Cabletel Holdings, L.P.              2,465,478                --

Kline Hawkes California SBIC, L.P.            1,703,652                --

The Union Labor Life Insurance                1,702,042                --
Company - Separate Account P

Robert I. Schwartz                               26,700            27,798

Kenneth M. & Susan F. Kiraly                     12,855                --

Richard P. Ruzzuti                                3,245                --

Bryant Hopper                                     1,217                --

Ronald S. Johnson                                 1,560                --

Lodwrick Cook                                        --            14,174

Peter Cracovaner                                  2,434                --

Richard Cunningham                                   --             7,411

Thomas O. FitzGerald                                 --             4,833

Wendy Foliano                                        --             3,222

Joseph Golden                                        --            44,418

Stephen Mayo                                         --            18,830

Karen Sancimino                                      --             4,833

Clinton Walker                                       --            36,109

                                       18
<PAGE>

                                   SCHEDULE C

          Name                             Class                      Shares
          ----                             -----                      ------
Arunas A. Chesonis               Class A Common Stock                 43,620
                                 Class B Common Stock              2,450,000

Jeffrey Sudikoff                 Class B Common Stock              1,200,048

Christopher Edgecomb Living      Class A Common Stock                145,000
Trust, dated April 25, 1998      Class B Common Stock              2,400,000

                                       19
<PAGE>

                                  SCHEDULE 3.1

          As of the date hereof, there were outstanding options to acquire an
aggregate of  1,967,437 shares of Class A Common Stock of the Corporation
pursuant to the PaeTec Corp. 1998 Incentive Compensation Plan.  In addition, on
the date hereof, there were outstanding warrants to purchase an aggregate of
40,000 shares of Class A Common Stock of the Corporation.

                                       20