<PAGE>

                                                                   Exhibit 10.58




                              CAIS INTERNET, INC.

                               VOTING AGREEMENT



     VOTING AGREEMENT, dated as of December 20, 1999 (the "Agreement"), among
CII Ventures LLC, a Delaware limited liability company ("CII"), and the
undersigned holders (each, a "Holder" and, collectively, the "Holders") of
shares of the common stock, par value $.01 (the "Company Common Stock"), of CAIS
Internet, Inc., a Delaware corporation (the "Company").


                                   RECITALS

     The Company and CII, propose to enter into a Preferred Stock Purchase
Agreement dated as of the date hereof (the "Purchase Agreement"; capitalized
terms not otherwise defined herein being used herein as therein defined),
pursuant to which CII initially desires to purchase 7,142,857 shares of the
Company's Series D Preferred Stock and obtain an option to purchase up to an
additional 7,142,857 shares of the Company's Series E Preferred Stock; and

     As a condition to entering into the Purchase Agreement, CII has requested
the Holders to agree, and the Holders have agreed, to enter into this Agreement.


                                   AGREEMENT

     NOW, THEREFORE, the parties hereto agree as follows:

     1.   Representations and Warranties of the Holders. Each Holder represents
          --------------------------------------------
and warrants to CII as to itself as follows:

     (a)  Ownership of Securities. The Holder is the record owner of
          -----------------------
the number of shares of Company Common Stock (the "Existing Securities")
(together with any shares of Company Common Stock hereafter acquired by the
Holder, the "Subject Securities") set forth on the signature page to this
Agreement opposite such Holder's name. The Holder does not own any securities of
the Company on the date hereof other than the Existing Securities. The Holder
has sole voting power (and the power to act by written consent) and sole power
to issue instructions with respect to the voting of the Existing Securities and
sole power of disposition of the Existing Securities and, on the record date
for, and on the date of the stockholders meeting of the Company held to vote on
(i) the issuance of shares of the Preferred Stock to CII (the "Share Issuance")
and (ii) the amendment to the Restated Certificate of Incorporation of the
Company to increase the authorized number of shares of preferred stock from 25
million to 50 million (the "Charter Amendment"), will have sole voting power
(and the power to act by written consent) and sole power to issue instructions
with respect to the voting of all of the Subject Securities and sole power of
disposition of the Subject Securities.
<PAGE>

                                                                               2

     (b)  Power; Binding Agreement. The Holder has full power and
          ------------------------
authority, or, if a natural person, legal capacity, to enter into and perform
all of its or his obligations under this Agreement. This Agreement has been duly
and validly executed and delivered by the Holder and constitutes a valid and
binding agreement of the Holder, enforceable against the Holder in accordance
with its terms, subject to the effects of bankruptcy, insolvency, fraudulent
conveyance, reorganization, moratorium and other similar laws relating to or
affecting creditors' rights generally, general equitable principles (whether
considered in a proceeding in equity or at law).

     (c)  No Conflicts. No filing with, and no permit, authorization, consent or
          ------------
approval of, any state or federal public body or authority or any other person
or entity is necessary for the execution of this Agreement by the Holder and the
consummation by the Holder of the transactions contemplated hereby, and neither
the execution and delivery of this Agreement by the Holder nor the consummation
by the Holder of the transactions contemplated hereby nor compliance by such
Holder with any of the provisions hereof will conflict with or result in any
breach of any applicable organizational documents or instruments applicable to
such Holder, result in a violation or breach of, or constitute (with or without
notice or lapse of time or both) a default (or give rise to any third-party
right of termination, cancellation, material modification or acceleration) under
any of the terms, conditions or provisions of any note, bond, mortgage,
indenture, license, contract, commitment, arrangement, understanding, agreement
or other instrument or obligation of any kind to which such Holder is a party or
by which the Holder's Subject Securities may be bound or violate any order,
writ, injunction, decree, judgment, order, statute, rule or regulation
applicable to the Holder as of the date hereof.

     (d)  No Liens. Except as set forth on Schedule 1(d), the Existing
          --------
Securities are held by the Holder, or by a nominee or custodian for the benefit
of the Holder, free and clear of all liens, claims, security interests, proxies,
voting trusts or agreements, understandings or arrangements or any other
encumbrances whatsoever, except for any encumbrances arising hereunder.

     2.   Agreement to Vote Shares.
          ------------------------

     (a)  At every meeting of the stockholders of the Company called with
respect to the Share Issuance and the Charter Amendment, and at every
adjournment thereof, and on every action or approval by written consent of the
stockholders of the Company with respect to the Share Issuance and the Charter
Amendment, each Holder irrevocably agrees that it shall vote all the Subject
Securities that it beneficially owns on the record date of any such vote or
action in favor of each of the Share Issuance and the Charter Amendment.

     (b)  Each of the Holders agrees to vote, or act by written consent with
respect to, any Subject Securities beneficially owned by him or it, at each
annual or special meeting of stockholders of the Company at which Directors (as
defined in the Stockholders Agreement) are to be elected or to take all actions
by written consent in lieu of any such meeting as are necessary, to cause the
designees of CII pursuant to Section 2.1 of the Stockholders Agreement to be
elected to the Board of Directors of the Company (the "Board"). Each of the
Holders
<PAGE>

                                                                               3

agrees to use his or its best efforts to cause the election of each such
designee to the Board, including nominating such individuals to be elected as
members of the Board as provided in the Stockholders Agreement.

     (c)  In the event that a vacancy is created at any time by the death,
disability, retirement, resignation or removal (with or without cause) of any
Director designated by CII (an "Investor Director"), the remaining Directors
shall cause the vacancy created thereby to be filled by a new designee of CII as
soon as possible and each Holder hereby agrees to take, at any time and from
time to time, all actions necessary to accomplish the same. Upon the written
request of the CII, each Holder shall vote, or act by written consent with
respect to, all Subject Securities beneficially owned by him or it and otherwise
take or cause to be taken all actions necessary to remove any Investor Director
and to elect any replacement Director designated as provided in the first
sentence of this Section 2(c). Unless CII shall otherwise request in writing, no
Holder shall take any action to cause the removal of any Investor Directors.

     (d)  Without the written consent of CII, each Holder agrees not to take any
action that would cause the number of Directors constituting the entire Board to
be other than eight (8) from and after the First Closing or nine (9) from and
after the Qualified Option Closing (as defined in the Stockholders Agreement) .

     (e)  In connection with any vote or action by written consent of the
stockholders of the Company relating to any matter specified in Section 2.3 of
the Stockholders Agreement, each Holder agrees, with respect to any Subject
Securities with respect to which he or it has the power to vote, (i) to vote
against (and not act by written consent to approve) such matter if such matter
has not been consented to by at least one Investor Director in accordance with
Section 2.3 of the Stockholders Agreement and (ii) to take or cause to be taken
all other reasonable actions required, to the extent permitted by law, to
prevent the taking of any action by the Company with respect to a matter unless
such matter has been consented to by at least one Investor Director in
accordance with Section 2.3 of the Stockholders Agreement.

     3.   Covenants of the Holder.  Each Holder hereby agrees and covenants
          -----------------------
that:

     (a) Restriction on Transfer, Proxies and Noninterference. In addition to
         ----------------------------------------------------
the transfer restrictions imposed by the Stockholders Agreement, until the
termination of such Holder's obligations under this Section 3(a) in accordance
with Section 12, such Holder shall not, directly or indirectly: (i) sell,
transfer, assign, pledge, encumber, hypothecate or similarly dispose of, or
enter into any contract, option or other arrangement or understanding with
respect to the sale, transfer, assignment, pledge, encumbrance, hypothecation or
similar disposition of, any of the Subject Securities or any options, rights or
warrants to acquire Subject Securities, except for such pledges as would be
permitted under Section 3.2(d) of the Stockholders Agreement if the Stockholders
Agreement were in effect as of the date hereof; (ii) grant any proxies or powers
of attorney, deposit any such Subject Securities or options, rights or warrants
to acquire Subject Securities into a voting trust or enter into a voting
agreement with respect to any of the Subject Securities; or (iii) take any
action that would make any representation or warranty contained herein untrue or
incorrect or have the effect of preventing or disabling the Holder from
performing its obligations under this Agreement.

<PAGE>

                                                                               4

     (b)  Cooperation. Each Holder shall use all reasonable efforts to cooperate
          -----------
with CII to effect the transactions contemplated by the Purchase Agreement and
provide any information reasonably requested by CII in connection with any
regulatory application or filing made or approval sought for such transactions.

     (c)  Stockholders Agreement.  Each Holder shall execute and deliver the
          ----------------------
Stockholders Agreement in the form attached as Exhibit D to the Purchase
Agreement on or prior to the First Closing Date.

     4.   Fiduciary Duties. Notwithstanding anything in this Agreement to the
          ----------------
contrary, the covenants and agreements set forth herein shall be subject to the
fiduciary obligations of each Holder or any of such Holder's designees now or
hereafter serving on the Board and shall not prevent any Holder or any of such
Holder's designees now or hereafter serving on the Board from taking any action
or refraining to take any action while acting in the capacity as a Director of
the Company.

     5.   Assignment; Benefits. This Agreement may not be assigned by
          --------------------
any party hereto without the prior written consent of the other party. This
Agreement shall be binding upon, and shall inure to the benefit of, each Holder,
CII and their respective successors and permitted assigns.

     6.   Notices. All notices and other communications given or made
          -------
pursuant hereto shall be in writing and shall be deemed to have been duly given
or made if and when delivered personally or by overnight courier or sent by
electronic transmission, with confirmation received, to the telecopy numbers
specified below:

     If to any of the Holders:

     c/o CAIS Internet, Inc.
     1255 22/nd/ Street, N.W., Fourth Floor
     Washington, D.C. 20037
     Telecopier No.:  202-463-7190
     Telephone No.:   202-715-1300
     Attention:  Gary Rabin, Executive
                 Vice President


     If to CII:

     c/o Kohlberg Kravis Roberts & Co. L.P.
     9 W. 57th Street
     New York, NY 10019
     Telephone:  (212) 750-8300
     Fax:  (212) 750-0333
     Attn:  Alexander Navab, Jr.

     With copies to:
<PAGE>

                                                                               5


     Simpson Thacher & Bartlett
     425 Lexington Avenue
     New York, New York 10017
     Telecopier No.: (212)455-2502
     Telephone No.: (212) 455-2000 Attention:
     David Sorkin, Esq.

or to such other address or telecopy number as any party may have furnished to
the other parties in writing in accordance herewith.

     7.   Notice of Litigation. Each Holder shall promptly notify CII of any
          --------------------
pending or, to its knowledge, threatened action or proceeding challenging the
validity or enforceability of this Agreement.

     8.   Specific Performance. The parties hereto agree that
          --------------------
irreparable harm would occur in the event that any of the provisions of this
Agreement were not performed in accordance with its specific terms or were
otherwise breached. It is accordingly agreed that the parties shall be entitled
to an injunction or injunctions to prevent breaches of this Agreement and to
enforce specifically the terms and provisions hereof in any court of the United
States or any state thereof having jurisdiction, this being in addition to any
other remedy to which they are entitled at law or in equity.

     9.   Amendment. This Agreement may not be amended or modified, except by an
          ---------
instrument in writing signed by or on behalf of each of the parties hereto. This
Agreement may not be waived by either party hereto, except by an instrument in
writing signed by or on behalf of the party granting such waiver.

     10.  Governing Law; Consent to Jurisdiction; Waiver of Jury Trial. This
          ------------------------------------------------------------
Agreement shall be governed in all respects by the laws of the State of New
York. No suit, action or proceeding with respect to this Agreement may be
brought in any court or before any similar authority other than in a court of
competent jurisdiction in the State of New York, and the parties hereto hereby
submit to the exclusive jurisdiction of such courts for the purpose of such
suit, proceeding or judgment. The parties hereto hereby irrevocably waive any
right which they may have had to bring such an action in any other court,
domestic or foreign, or before any similar domestic or foreign authority. Each
of the parties hereto hereby irrevocably and unconditionally waives trial by
jury in any legal action or proceeding in relation to this Agreement and for any
counterclaim therein.

     11.  Counterparts. This Agreement may be executed in counterparts, each of
          ------------
which shall be deemed an original, but all of which together shall constitute
one and the same agreement.

     12.  Termination. Sections 2(a) and 3(a) of this Agreement shall terminate
          -----------
upon the earlier of (i) the termination of the Purchase Agreement pursuant to
its terms and (ii) the later of (A) approval of the Share Issuance by the
requisite vote of the stockholders of the Company
<PAGE>

                                                                               6

and (B) the First Closing Date. The remaining provisions of this Agreement shall
terminate upon the earlier of (i) the termination of the Purchase Agreement
pursuant to its terms and (ii) the termination of the Stockholders Agreement
pursuant to its terms. Nothing herein shall relieve any party from any liability
for such party's wilful breach of this Agreement and nothing herein shall limit,
restrict, impair, amend or otherwise modify the rights, remedies, obligations or
liabilities of any person under any other contract or agreement, including,
without limitation, the Purchase Agreement or the Stockholders Agreement.

     13.  Severability. Any term or provision of this Agreement which is invalid
          ------------
or unenforceable in any jurisdiction shall, as to that jurisdiction, be
ineffective to the extent of such invalidity or unenforceability and shall not
render invalid or unenforceable the remaining terms and provisions of this
Agreement or affect the validity or enforceability of any of the terms or
provisions of this Agreement in any other jurisdiction. If any provision of this
Agreement is so broad as to be unenforceable, the provision shall be interpreted
to be only so broad as is enforceable.
<PAGE>

                                                                               7

     IN WITNESS WHEREOF, this Agreement has been executed by or on behalf of
each of the parties hereto, all as of the date first above written.

                                CII VENTURES LLC


                                    /s/ Alex Narab
                                By:__________________________________
                                     Name: Alex Narab
                                     Title:



                                HOLDERS


                                /s/ ULYSSES G. AUGER, SR.
                                _____________________________________
                                ULYSSES G. AUGER, SR.
                                Shares of Company Common Stock: 4,808,704



                                /s/ ULYSSES G. AUGER, II
                                _____________________________________
                                ULYSSES G. AUGER, II
                                Shares of Company Common Stock: 4,824,214

                                CHANCERY LANE, L.P.
                                Shares of Company Common Stock: 2,726,480


                                    /s/ signature illegible
                                By:_____________________________________
                                    General Partner


                                    /s/ signature illegible
                                By:_____________________________________
                                    Name:
                                    Title:


                                /s/ WILLIAM M. CALDWELL
                                _____________________________________
                                WILLIAM M. CALDWELL
                                Shares of Company Common Stock:  - 0 -






                                _______________________________________
<PAGE>

                                                                               8


                                /s/ EVANS K. ANDERSON
                                ______________________________________
                                EVANS K. ANDERSON
                                Shares of Company Common Stock:  - 0 -


                                /s/ GARY H. RABIN
                                _____________________________________
                                GARY H. RABIN
                                Shares of Company Common Stock:  - 0 -



                                _____________________________________
                                KEVIN BRAND
                                Shares of Company Common Stock:_______