--------------------------------------------------------------------------------
--------------------------------------------------------------------------------

                               WARRANT AGREEMENT
    
                           Dated as of April 23, 1999     

                                 by and between

                              CAIS Internet, Inc.

                                      and

                           Hilton Hotels Corporation

    
     THIS WARRANT AGREEMENT (this "Agreement") is made and entered into as of
                                   ---------                                 
April 23, 1999, by and between CAIS Internet, Inc., a Delaware corporation (the
"Company"), and Hilton Hotels Corporation, a Delaware corporation ("Hilton" or
 -------                                                                      
"Initiating Holder").  Certain capitalized terms used herein are defined in
Section 2.11.     

                                 RECITALS
                                 --------
    
     This Agreement is made pursuant to the First Amendment to the Master
License Agreement (the "Amendment"), dated April 23, 1999, by and between the
                        ---------                                            
Company, CAIS, Inc. and Hilton, relating to, among other things, the issuance by
the Company of a Common Stock warrant (the "Warrant") to Hilton, representing
                                            -------                          
the right to purchase 66,667 shares of Common Stock, par value $.01 per share
(the "Common Stock"), as such number may be adjusted pursuant to the terms of
      ------------                                                           
the Warrant.     

     As a further inducement to and a condition of the Amendment, the Company
and Hilton have agreed to enter into this Agreement to grant Hilton the rights
provided herein.

     NOW, THEREFORE, in consideration of the promises of the parties set forth
herein, the parties hereby covenant and agree as follows:

                                       1
<PAGE>
 
                                   SECTION 1

                              Registration Rights
                              -------------------

     1.1  Requested Registration.
          ---------------------- 

          (a)  Request for Registration.  In case the Company shall receive from
               ------------------------                                         
Initiating Holder a written request that the Company effect any registration,
qualification or compliance with respect to all, but not less than all, of
Initiating Holder's Registrable Securities, the Company will:

               (i)   promptly give written notice of the proposed registration,
qualification or compliance to all other Holders; and

               (ii)  as soon as practicable, use its commercially reasonable 
efforts to effect such registration, qualification or compliance (including,
without limitation, appropriate qualification under applicable blue sky or other
state securities laws and appropriate compliance with applicable regulations
issued under the Securities Act and any other governmental requirements or
regulations) as may be so requested and as would permit or facilitate the sale
and distribution of all or such portion of such Registrable Securities as are
specified in such request, together with all or such portion of the Registrable
Securities of any Holder or Holders joining in such request as are specified in
a written request received by the Company within 20 days after receipt of such
written notice from the Company;

          Provided, however, that the Company shall not be obligated to take any
action to effect any such registration, qualification or compliance pursuant to
this Section 1.1:

                    (A)  in any particular jurisdiction in which the Company
would be required to execute a general consent to service of process in
effecting such registration, qualification or compliance unless the Company is
already subject to service in such jurisdiction and except as may be required by
the Securities Act;

                    (B)  prior to six months after the closing date for the
Company's initial public offering of its Common Stock;

                    (C)  during the period starting with the date which is 30
days prior to the Company's estimated date of filing of, and ending on the date
60 days immediately following the effective date of, any registration statement
pertaining to securities of the Company (other than a registration of securities
in a Commission Rule 145 transaction or with respect to an employee benefit
plan), provided that the Company is actively employing in good faith all
reasonable efforts to cause such registration statement to become effective;
provided, however, that the Company may not exercise this deferral right more
than once per 12-month period;

                                       2
<PAGE>
 
                    (D)  after the Company has effected one such registration
pursuant to this Section 1.1(a), and such registration has been declared or
ordered effective; or

                    (E)  if the Company shall furnish to such Holders a
certificate signed by the President of the Company stating that in the good
faith judgment of the Board of Directors it would be seriously detrimental to
the Company or its stockholders for a registration statement to be filed in the
near future (in which case the Company's obligation to use its best efforts to
register, qualify or comply under this Section 1.1 shall be deferred for a
period not to exceed 90 days from the date of receipt of written request from
Initiating Holder; provided, however, that the Company may not exercise this
deferral right more than once per 12-month period).

          (b)  Underwriting.  In the event that a registration pursuant to this
               ------------                                                    
Section 1.1 is for a registered public offering involving an underwriting, the
Company shall so advise the Holders as part of the notice given pursuant to
Section 1.1(a)(i).  In such event, the right of any Holder to registration
pursuant to Section 1.1(b) shall be conditioned upon such Holder's participation
in the underwriting arrangements required by this Section 1.1, and the inclusion
of such Holder's Registrable Securities in the underwriting to the extent
requested shall be limited to the extent provided herein.

          The Company shall (together with all Holders proposing to distribute
their securities through such underwriting) enter into an underwriting agreement
in customary form with the managing underwriter selected for such underwriting
by the Initiating Holder, but subject to the Company's reasonable approval.
Notwithstanding any other provision of this Section 1.1, if the managing
underwriter advises the Initiating Holder in writing that marketing factors
require a limitation of the number of shares to be underwritten, then the
Company shall so advise all holders of Registrable Securities and the number of
shares of Registrable Securities that may be included in the registration and
underwriting shall be allocated among all Holders in proportion, as nearly as
practicable, to the respective amounts of Registrable Securities held by such
Holders at the time of filing the registration statement.  No Registrable
Securities excluded from the underwriting by reason of the underwriter's
marketing limitation shall be included in such registration.  To facilitate the
allocation of shares in accordance with the above provisions, the Company or the
underwriters may round the number of shares allocated to any Holder to the
nearest 100 shares. Prior to excluding any Registrable Securities from any
underwriting pursuant to this paragraph, the Company shall exclude from such
underwriting all securities that are not Registrable Securities.

          If any Holder of Registrable Securities disapproves of the terms of
the underwriting, such person may elect to withdraw therefrom by written notice
to the Company, the managing underwriter and the Initiating Holder.  The
Registrable Securities and/or other securities so withdrawn shall also be
withdrawn from registration, and such Registrable Securities shall not be
transferred in a public distribution prior to 90 days after the effective date
of such registration, or such other shorter period of time as the underwriters
may require.

                                       3
<PAGE>
 
     1.2  Company Registration.
          -------------------- 

          (a)  Notice of Registration.  If at any time or from time to time the
               ----------------------                                          
Company shall determine to register any of its securities following the initial
public offering of the Company's Common Stock, either for its own account or for
the account of a security holder or holders, other than (i) a registration
relating solely to employee benefit plans or other compensatory plans or
arrangements, or (ii) a registration relating solely to a Commission Rule 145
transaction, the Company will:

               (i)   promptly give to each Holder written notice thereof, and

               (ii)  include in such registration (and any related qualification
under blue sky laws or other compliance), and in any underwriting involved
therein, all the Registrable Securities specified in a written request or
requests, made within 20 days after receipt of such written notice from the
Company, by any Holder.

          (b)  Underwriting.  If the registration of which the Company gives
               ------------                                                 
notice is for a registered public offering involving an underwriting, the
Company shall so advise the Holders as a part of the written notice given
pursuant to Section 1.2(a)(i).  In such event the right of any Holder to
registration pursuant to Section 1.2 shall be conditioned upon such Holder's
participation in such underwriting and the inclusion of Registrable Securities
in the underwriting to the extent provided herein.  All Piggyback Holders
proposing to distribute their securities through such underwriting shall
(together with the Company and the other holders distributing their securities
through such underwriting) enter into an underwriting agreement in customary
form with the managing underwriter selected for such underwriting by the
Company.  Notwithstanding any other provision of this Section 1.2, if the
managing underwriter determines that marketing factors require a limitation of
the number of shares to be underwritten, the managing underwriter and the
Company may reduce the Registrable Securities to be included in such
registration to the extent the underwriters deem necessary; provided, however,
that any Registrable Securities held by the Piggyback Holders proposed to be
included in the registration and underwriting shall be reduced to zero prior to
any reductions with respect to Registrable Securities held by any other holders.
The Company shall so advise all Holders and other holders distributing their
securities through such underwriting that the number of shares of Registrable
Securities that may be included in the registration and underwriting shall be
allocated among all the Holders in proportion, as nearly as practicable, to the
respective amounts of Registrable Securities held by such Holder at the time of
filing the Registration Statement.  To facilitate the allocation of shares in
accordance with the above provisions, the Company may round the number of shares
allocated to any Holder or holder to the nearest 100 shares.  If any Holder
disapproves of the terms of any such underwriting, he may elect to withdraw
therefrom by written notice to the Company and the managing underwriter.  Any
securities excluded or withdrawn from such underwriting shall be withdrawn from
such registration, and shall not be transferred in a public distribution prior
to 90 days after the effective date of the registration statement relating
thereto, or such other shorter period of time as the underwriters may require.

                                       4
<PAGE>
 
          (c)  Right to Terminate Registration.  The Company shall have the 
               -------------------------------                 
right to terminate or withdraw any registration initiated by it under this
Section 1.2 prior to the effectiveness of such registration whether or not any
Holder has elected to include securities in such registration.

     1.3  Registration on Form S-3.
          ------------------------ 

          (a)  If any Holder or Holders request that the Company file a shelf
registration statement on Form S-3 (or any successor form to Form S-3) for a
public offering of Registrable Securities, and the Company is a registrant
entitled to use Form S-3 to register the Registrable Securities for such an
offering, the Company shall use its best efforts to cause such Registrable
Securities to be registered for the offering on such form and to cause such
Registrable Securities to be qualified in such jurisdictions as such Holder or
Holders may reasonably request; provided, however, that the Company shall not be
required to effect more than one registration pursuant to this Section 1.3.  The
Company shall inform other Holders of the proposed registration and offer them
the opportunity to participate.  The substantive provisions of Section 1.3(b)
shall be applicable to each registration initiated under this Section 1.3.

          (b)  Notwithstanding the foregoing, the Company shall not be obligated
to take any action pursuant to this Section 1.3 (i) in any particular
jurisdiction in which the Company would be required to execute a general consent
to service of process in effecting such registration, qualification or
compliance unless the Company is already subject to service in such jurisdiction
and except as may be required by the Securities Act; (ii) prior to the Company's
first registered public offering of its stock; (iii) during the period starting
with the date 30 days prior to the Company's estimated date of filing of, and
ending on the date 60 days immediately following, the effective date of any
registration statement pertaining to securities of the Company (other than a
registration of securities in a Commission Rule 145 transaction or with respect
to an employee benefit plan), provided that the Company is actively employing in
good faith all reasonable efforts to cause such registration statement to become
effective; provided, however, that the Company may not exercise this deferral
right more than once in any 12-month period; or (iv) if the Company shall
furnish to such Holder a certificate signed by the President of the Company
stating that in the good faith judgment of the Board of Directors it would be
seriously detrimental to the Company or its stockholders for registration
statements to be filed in the near future, then, in each case, the Company's
obligation to use its best efforts to file a registration statement shall be
deferred for a period not to exceed 90 days from the receipt of the request to
file such registration by such Holder; provided, however, that the Company may
not exercise this deferral right more than once in any 12-month period.

     1.4  Relationship to Other Registration Rights.  The registration rights
          -----------------------------------------                          
granted pursuant to Section 1.2 are subordinate to the registration rights
granted by the Company to the extent provided in that certain Warrant
Registration Rights Agreement, dated as of September 4, 1998, by and among the
Company, Cleartel Communications, Inc., CAIS, Inc. and ING (U.S.) Capital
Corporation.

                                       5
<PAGE>
 
     1.5  Expenses of Registration.  All Registration Expenses incurred in
          ------------------------                                        
connection with (i) one registration pursuant to Section 1.1 and (ii) all
registrations pursuant to Section 1.2 and 1.3 shall be borne by the Company.
Unless otherwise stated, all Selling Expenses relating to securities registered
on behalf of the Holders and all other Registration Expenses shall be borne by
the Holders of such securities pro rata on the basis of the number of shares so
registered.

     1.6  Registration Procedures.  In the case of each registration,
          -----------------------                                    
qualification or compliance effected by the Company pursuant to this Section 1,
the Company will keep each Holder advised in writing as to the initiation of
each registration, qualification and compliance and as to the completion
thereof.  At its expense the Company will:

          (a)  Prepare and file with the Commission a registration statement
with respect to such securities and use its best efforts to cause such
registration statement to become and remain effective for at least 180 days or
until the distribution described in the Registration Statement has been
completed;

          (b)  Furnish to the Holders participating in such registration and to
the underwriters of the securities being registered such reasonable number of
copies of the registration statement, preliminary prospectus, final prospectus
and such other documents as such underwriters may reasonably request in order to
facilitate the public offering of such securities;

          (c)  Furnish to the Holders (i) an opinion of counsel for the Company,
dated the effective date of the registration statement, and (ii) subject to the
accountants obtaining the necessary representations as specified in Statement on
Auditing Standards No. 72, a "comfort" letter signed by the independent public
accountants who have certified the Company's financial statements included in
the registration statement, covering substantially the same matters with respect
to the registration statement (and the prospectus included therein) and, in the
case of such accountants' letter, with respect to changes subsequent to the date
of such financial statements, as are customarily covered in opinions of issuer's
counsel and in accountants' letters delivered to the underwriters in
underwritten public offerings of securities.

          (d)  From time to time take all action which may be necessary so that
the Warrant Shares, immediately upon their issuance upon the exercise of the
Warrant, will be listed on the principal securities exchanges and markets within
the United States (including The Nasdaq National Market), if any, on which other
shares of the Company's Common Stock are then listed, if any; and


          (e)  Notify the Holders of Registrable Securities to be sold and the
managing underwriters, if any, promptly, and (if requested by any such person)
confirm such notice in writing, (i)(A) when a prospectus or any prospectus
supplement or post-effective amendment is proposed to be filed, and (B) with
respect to a registration statement or any post-effective amendment, when the
same has become effective, (ii) of any request by the Commission or any other
Federal or state governmental authority for amendments or supplements to a
registration statement or related prospectus or for additional information,
(iii) of the issuance by the Commission, any state securities commission, any
other governmental 

                                       6
<PAGE>
 
agency or any court of any stop order suspending the effectiveness of such
registration statement or of any order or injunction suspending or enjoining the
use of a prospectus or the effectiveness of a registration statement or the
initiation of any proceedings for that purpose, (iv) of the receipt by the
Company of any notification with respect to the suspension of the qualification
or exemption from qualification of any of the Registrable Securities for sale in
any jurisdiction, or the initiation or threatening of any proceeding for such
purpose, and (v) of the happening of any event, the existence of any information
becoming known that makes any statement made in a registration statement or
related prospectus or any document incorporated or deemed to be incorporated
therein by reference untrue in any material respect or omit to state any
material fact required to be stated therein or necessary to make the statements
therein, not misleading. The Company represents and warrants to, and agrees
with, Hilton that each registration statement and prospectus relating to
Registrable Securities will not contain any untrue statement of a material fact
or omit to state any material fact required to be stated therein or necessary to
make the statements therein, in light of the circumstances under which they were
made, not misleading; provided, that such representation and warranty shall not
extend to any written information furnished by or on behalf of any Holder for
inclusion in any such registration statement or prospectus.

     1.7  Indemnification.
          --------------- 

          (a)  The Company will indemnify each Holder, each of its officers and
directors and partners, and each person controlling such Holder within the
meaning of Section 15 of the Securities Act, with respect to which registration,
qualification or compliance has been effected pursuant to this Section 1, and
each underwriter, if any, and each person who controls any underwriter within
the meaning of Section 15 of the Securities Act, against all expenses, claims,
losses, damages or liabilities (or actions in respect thereof), including any of
the foregoing incurred in settlement of any litigation, commenced or threatened,
arising out of or based on any untrue statement (or alleged untrue statement) of
a material fact contained in any registration statement, prospectus, offering
circular or other document, or any amendment or supplement thereto, incident to
any such registration, qualification or compliance, or based on any omission (or
alleged omission) to state therein a material fact required to be stated therein
or necessary to make the statements therein, in light of the circumstances in
which they were made, not misleading, or any violation by the Company of the
Securities Act, the Exchange Act, state securities law or any rule or regulation
promulgated under such laws applicable to the Company in connection with any
such registration, qualification or compliance, and within a reasonable period
the Company will reimburse each such Holder, each of its officers and directors,
and each person controlling such Holder, each such underwriter and each person
who controls any such underwriter, for any legal and any other expenses
reasonably incurred in connection with investigating, preparing or defending any
such claim, loss, damage, liability or action; provided, however, that the
Company will not be liable in any such case to the extent that any such claim,
loss, damage, liability or expense arises out of or is based on any untrue
statement or omission or alleged untrue statement or omission made in reliance
upon and in conformity with written information furnished to the Company by an
instrument duly executed by such Holder, controlling person or underwriter and
stated to be specifically for use therein.

                                       7
<PAGE>
 
          (b)  Each Holder will, if Registrable Securities held by such Holder
are included in the securities as to which such registration, qualification or
compliance is being effected, indemnify the Company, each of its directors and
officers, each underwriter, if any, of the Company's securities covered by such
a registration statement, each person who controls the Company or such
underwriter within the meaning of Section 15 of the Securities Act, and each
other such Holder, each of its officers and directors and each person
controlling such Holder within the meaning of Section 15 of the Securities Act,
against all claims, losses, damages and liabilities (or actions in respect
thereof) arising out of or based on any untrue statement (or alleged untrue
statement) of a material fact contained in any such registration statement,
prospectus, offering circular or other document, or any omission (or alleged
omission) to state therein a material fact required to be stated therein or
necessary to make the statements therein not misleading, and within a reasonable
period will reimburse the Company, such Holders, such directors, officers,
persons, underwriters or control persons for any legal or any other expenses
reasonably incurred in connection with investigating or defending any such
claim, loss, damage, liability or action, in each case to the extent, but only
to the extent, that such untrue statement (or alleged untrue statement) or
omission (or alleged omission) is made in such registration statement,
prospectus, offering circular or other document in reliance upon and in
conformity with written information furnished to the Company by an instrument
duly executed by such Holder and stated to be specifically for use therein.
Notwithstanding the foregoing, the liability of each Holder under this
subsection (b) shall be limited in an amount equal to the gross proceeds before
expenses and commissions to each Holder received for the shares sold by such
Holder.

          (c)  Each party entitled to indemnification under this Section 1.6
(the "Indemnified Party") shall give notice to the party required to provide
      -----------------                                                     
indemnification (the "Indemnifying Party") promptly after such Indemnified Party
                      ------------------                                        
has actual knowledge of any claim as to which indemnity may be sought, and shall
permit the Indemnifying Party to assume the defense of any such claim or any
litigation resulting therefrom, provided that counsel for the Indemnifying
Party, who shall conduct the defense of such claim or litigation, shall be
approved by the Indemnified Party (whose approval shall not unreasonably be
withheld), and the Indemnified Party may participate in such defense at such
party's expense, and provided further that the failure of any Indemnified Party
to give notice as provided herein shall not relieve the Indemnifying Party of
its obligations under this Section 1 unless the failure to give such notice is
materially prejudicial to an Indemnifying Party's ability to defend such action
and provided further, that the Indemnifying Party shall not assume the defense
for matters as to which there is a conflict of interest or separate and
different defenses.  Rather, where such a conflict of interest or separate and
different defenses shall exist, the Indemnified Party may appoint its own
counsel; provided, however, that in no event shall the Indemnifying Party be
liable for the fees and expenses of more than one counsel (in addition to any
local counsel) separate from their own counsel for the Indemnified Party in
connection with any one action or separate but similar or related actions in the
same jurisdiction arising out of the same general allegations or circumstances.
No Indemnifying Party, in the defense of any such claim or litigation, shall,
except with the consent of each Indemnified Party, consent to entry of any
judgment or enter into any settlement which does not include as an unconditional
term thereof the giving by the claimant or plaintiff to such Indemnified Party
of a release from all liability in respect to such claim or litigation.

                                       8
<PAGE>
 
     1.8  Information by Holder.  The Holder or Holders of Registrable
          ---------------------                                       
Securities included in any registration shall furnish to the Company such
information regarding such Holder or Holders, the Registrable Securities held by
them and the distribution proposed by such Holder or Holders as the Company may
request in writing and as shall be required in connection with any registration,
qualification or compliance referred to in this Section 1.

     1.9  Rule 144 Reporting.  With a view to making available the benefits of
          ------------------                                                  
certain rules and regulations of the Commission which may at any time permit the
sale of the Restricted Securities to the public without registration, after such
time as a public market exists for the Common Stock of the Company, the Company
agrees to use its best efforts to:

          (a)  make and keep public information available, as those terms are
understood and defined in Commission Rule 144 under the Securities Act, at all
times after the effective date that the Company becomes subject to the reporting
requirements of the Securities Act or the Exchange Act;

          (b)  file with the Commission in a timely manner all reports and other
documents required of the Company under the Securities Act and the Exchange Act
(at any time after it has become subject to such reporting requirements); and

          (c)  furnish to the Holder or beneficial owner of Registrable
Securities forthwith upon request a written statement by the Company as to its
compliance with the reporting requirements of Commission Rule 144 (at any time
after 90 days after the effective date of the first registration statement filed
by the Company for an offering of its securities to the general public), and of
the Securities Act and the Exchange Act (at any time after it has become subject
to such reporting requirements), a copy of the most recent annual or quarterly
report of the Company and such other reports and documents of the Company and
other information in the possession of or reasonably obtainable by the Company
as such Holder of Registrable Securities may reasonably request in availing
itself of any rule or regulation of the Commission allowing such Holder of
Registrable Securities to sell any such securities without registration.

     1.10  Transfer of Registration Rights.  The rights to cause the Company to
           -------------------------------                                     
register securities granted under Sections 1.1, 1.2 and 1.3 may be assigned to
any permitted transferee or assignee of Registrable Securities.

     1.11  Termination of Registration Rights.  The registration rights granted
           ----------------------------------                                  
shall terminate as to the Holder at such time as the Company's Common Stock is
listed on a national securities exchange or quoted on an automated quotation
system and all Registrable Securities held by such Holder may, in the opinion of
counsel to the Company (which opinion shall be addressed and rendered to such
Holder), be sold within a given three-month period pursuant to Commission Rule
144.

                                       9
<PAGE>
 
                                   SECTION 2

                                 "Put" Option
                                 ------------

     2.1  "Put" Option.  Commencing upon the effective date of the registration
          ------------                                                         
statement for the initial public offering of the Company's Common Stock, Hilton
shall have a "put" option to sell the Warrant, or if exercised, Warrant Shares,
to the Company or CAIS, Inc., and, in such event, the Company and/or CAIS, Inc.
shall be required to purchase such securities from Hilton.  The option exercise
price payable to Hilton in such event shall equal the product of (1) the initial
public offering price for the Company's Common Stock times (2) the Warrant
Shares subject to such option.  The "put" option shall expire ninety (90) days
following the earlier of: (1) the effective date of the first registration
statement that includes any Registrable Securities for resale and (2) the date
on which Hilton may sell all of the Warrant Shares within a three-month period
pursuant to Commission Rule 144.

                                   SECTION 3

                                   Opinions
                                   --------
                                        
     3.1  Opinions.  Upon the effectiveness of the Company's registration
          --------                                                       
statement with respect the initial public offering of its Common Stock, the
Company shall cause outside counsel to the Company to deliver to Hilton an
opinion, addressed to Hilton, in form and substance reasonably satisfactory to
Hilton, covering such matters as are customary in transactions of this nature,
including, without limitation, opinions to the effect that the grant of the
Warrant and the issuance of the Warrant Shares upon the exercise thereof (1) do
not require registration under the Securities Act and (2) will not be integrated
with the Company's initial public offering.  Notwithstanding any other provision
of this Agreement or of the Warrant, in the event that the opinion contemplated
by this Section 3 shall not be delivered as of the date required by this 
Section 3, the Initiating Holder's sole remedy shall be the right to exercise 
the put option pursuant to Section 2.1 above.

                                   SECTION 4

                                 Miscellaneous
                                 -------------

     4.1  Governing Law.  This Agreement shall be governed in all respects by
          -------------                                                      
the internal laws of the State of Delaware, excluding the conflicts of law
provisions thereof.

     4.2  Jurisdiction; Jury Trial Waiver.  THE PARTIES HEREBY WAIVE ALL RIGHTS
          -------------------------------                                      
TO TRIAL BY JURY IN ANY ACTION OR PROCEEDING INSTITUTED BY ANY PARTY AGAINST ANY
OTHER PARTY ARISING ON, OUT OF OR BY REASON OF THIS AGREEMENT, ANY ALLEGED
TORTIOUS CONDUCT BY ANY PARTY OR IN ANY WAY, DIRECTLY OR INDIRECTLY, ARISING OUT
OF OR RELATED TO THE RELATIONSHIP BETWEEN THE PARTIES.

                                       10
<PAGE>
 
     4.3  Survival.  The representations, warranties, covenants and agreements
          --------                                                            
made herein shall survive any investigation made by the Holders of Registrable
Securities and the closing of the transactions contemplated hereby.

     4.4  Successors and Assigns.  Except as otherwise provided herein, the
          ----------------------                                           
provisions hereof shall inure to the benefit of, and be binding upon, the
successors, permitted assigns, heirs, executors and administrators of the
parties hereto.

     4.5  Entire Agreement; Amendment.  This Agreement and the other documents
          ---------------------------                                         
delivered pursuant hereto constitute the full and entire understanding and
agreement between the parties with regard to the subjects hereof and thereof,
and no party shall be liable or bound to any other party in any manner by any
warranties, representations or covenants except as specifically set forth herein
or therein.  Except as expressly provided herein, neither this Agreement nor any
term hereof may be amended, waived, discharged or terminated other than by a
written instrument signed by the party against whom enforcement of any such
amendment, waiver, discharge or termination is sought.

     4.6  Notices, etc.  All notices and other communications required or
          -------------                                                  
permitted hereunder shall be in writing and shall be mailed by registered or
certified mail, postage prepaid, or otherwise delivered by hand or by messenger,
addressed (a) if to a Holder, at such Holder's address, as shown on the stock
records of the Company, or at such other address as such Holder shall have
furnished to the Company in writing, or (b) if to the Company, at such address
as the Company shall have furnished to the Holders in writing, and addressed to
the attention of the President.  Each such notice or other communication shall
for all purposes of this Agreement be treated as effective or having been given
when delivered if delivered personally, or, if sent by mail, at the earlier of
its receipt or 72 hours after the same has been deposited in a regularly
maintained receptacle for the deposit of the United States mail, addressed and
mailed as aforesaid.

     4.7  Delays or Omissions.  Except as expressly provided herein, no delay
          -------------------                                                
or omission to exercise any right, power or remedy accruing to any party to this
Agreement upon any breach or default of any other party under this Agreement,
shall impair any such right, power or remedy of such nondefaulting party nor
shall it be construed to be a waiver of any such breach or default, or an
acquiescence therein, or of or in any similar breach or default thereafter
occurring; nor shall any waiver of any single breach or default be deemed a
waiver of any other breach or default theretofore or thereafter occurring.  Any
waiver, permit, consent or approval of any kind or character on the part of any
party of any breach or default under this Agreement, or any waiver on the part
of any holder of any provisions or conditions of this Agreement, must be in
writing and shall be effective only to the extent specifically set forth in such
writing.  All remedies, either under this Agreement or by law or otherwise
afforded to any party to this Agreement, shall be cumulative and not
alternative.

     4.8  Counterparts.  This Agreement may be executed in any number of
          ------------                                                  
counterparts, each of which shall be enforceable against the parties actually
executing such counterparts, and all of which together shall constitute one
instrument.

                                       11
<PAGE>
 
     4.9  Severability.  In the event that any provision of this Agreement
          ------------                                                    
becomes or is declared by a court of competent jurisdiction to be illegal,
unenforceable or void, this Agreement shall continue in full force and effect
without said provision; provided, however, that no such severability shall be
effective if it materially changes the economic benefit of this Agreement to any
party.

     4.10  Titles and Subtitles.  The titles and subtitles used in this
           --------------------                                        
Agreement are used for convenience only and are not considered in construing or
interpreting this Agreement.

     4.11  Certain Definitions.  As used in this Agreement, the following terms
           -------------------                                                 
shall have the following respective meanings:

          "Board of Directors" means the Board of Directors of the Company in
           ------------------                                                
office at the applicable time.

          "Closing Date" means the date of the issue of the Warrant.
           ------------                                             

          "Common Stock" has the meaning ascribed to such term in the preamble
           ------------                                                       
hereof.

          "Commission" means the Securities and Exchange Commission or any 
           ----------                                                
other federal agency at the time administering the Securities Act.

          "Exchange Act" means the Securities Exchange Act of 1934, as amended,
           ------------                                                        
or any similar federal statute and the rules and regulations of the Commission
thereunder, all as the same shall be in effect at the time.

          "Holder" means (i) any Person holding Registrable Securities and (ii)
           ------                                                              
any Person holding Registrable Securities to whom the rights under Section 1
have been transferred in accordance with Section 1.10 hereof.

          "Initiating Holder" means Hilton Hotels Corporation and its permitted
           -----------------                                                   
successors and assigns as Holders of Registrable Securities requesting that
Registrable Securities owned thereby be included in a registration statement
pursuant to Section 1.1.

          "Person" means an individual, corporation, partnership, trust, 
           ------                                                  
limited liability company or other entity, or a government or any agency or
political subdivision thereof.

          "Piggyback Holders" means any Holders requesting that Registrable
           -----------------                                               
Securities owned thereby be included in a registration statement pursuant to
Section 1.2.

          "Registrable Securities" means the Warrant Shares and any other
           ----------------------                                        
securities issued or issuable in respect to any Warrant Shares by way of a stock
split, stock dividend, or in connection with a combination of shares,
recapitalization, merger, consolidation or other reorganization or otherwise;
provided, however, that such Warrant Shares or other securities 

                                       12
<PAGE>
 
shall only be treated as Registrable Securities until (i) they have been
effectively registered under the Securities Act and disposed of pursuant to an
effective registration statement, or (ii) they are sold under circumstances in
which all of the applicable conditions under Rule 144 (or any similar provisions
then in force) under the Securities Act are met, including a sale pursuant to
the provisions of Rule 144(k).

          The terms "register," "registered" and "registration" refer to a
                     --------    ----------       ------------            
registration effected by preparing and filing a registration statement in
compliance with the Securities Act, and the declaration by the Commission of the
effectiveness of such registration statement.

          "Registration Expenses" means all expenses, except as otherwise stated
           ---------------------                                                
below, incurred by the Company in complying with Sections 1.1, 1.2 and 1.3
hereof, including, without limitation, all registration, qualification and
filing fees, printing expenses, escrow fees, fees and disbursements of counsel
for the Company, blue sky fees and expenses, the expense of any special audits
or "comfort letters" incident to or required by any such registration (but
excluding the compensation of regular employees of the Company which shall be
paid in any event by the Company) and the reasonable fees and disbursements of
one counsel for all Holders.

          "Restricted Securities" means the securities of the Company required
           ---------------------                                              
to bear certain legends.

          "Securities Act" means the Securities Act of 1933, as amended, or any
           --------------                                                      
similar federal statute and the rules and regulations of the Commission
thereunder, all as the same shall be in effect at the time.

          "Selling Expenses" means all underwriting discounts, selling
           ----------------                                           
commissions and stock transfer taxes applicable to the securities registered by
the Holders.

          "Warrant Shares" means the shares of Common Stock delivered or
           --------------                                               
deliverable upon exercise of the Warrants.

          "Warrant" has the meaning ascribed to such term in the preamble
           -------                                                       
hereof.

                     [This space intentionally left blank]

                                       13
<PAGE>
 
     The foregoing Agreement is hereby executed as of the date first above
written.

                              "COMPANY"

                              CAIS INTERNET, INC.,
                              a Delaware corporation

    
                              By: /s/ William M. Caldwell, IV        
                                  ------------------------------------
                                  William M. Caldwell, IV
                                  President


                              "INITIATING HOLDER"

                              HILTON HOTELS CORPORATION,
                              a Delaware corporation
    
                              By: /s/ Dennis Koci
                                  ------------------------------------
                                  Name:  Dennis Koci
                                  Title: Senior Vice President     




 

                                       14

Source: OneCLE Business Contracts.