
<PAGE>
 
                                                                  EXHIBIT 10.7

                              CRITICAL PATH, INC.

                       AMENDMENT TO AMENDED AND RESTATED
                          INVESTORS' RIGHTS AGREEMENT


     THIS AMENDMENT TO AMENDED AND RESTATED INVESTORS' RIGHTS AGREEMENT (the
"Amendment") is made as of January 13, 1999, by and among CRITICAL PATH, INC., a
California corporation (the "Company"), and those investors in the Company
listed on Exhibit A attached hereto (the "Series B Investors"), those
shareholders of the Company listed on Exhibit B attached hereto (the "Series A
Shareholders") and those founders listed on Exhibit C attached hereto (the
"Founders").  The Series B Investors, the Series A Shareholders and the Founders
are referred to herein individually as "Investor" and collectively as the
"Investors."

     RECITALS:

     A.  The Company and certain Investors have entered into that certain
Amended and Restated Investors' Rights Agreement dated September 11, 1998 (the
"Investors' Rights Agreement") in connection with the Series B Preferred Stock
Financing in which the Company sold and certain Investors purchased shares of
Series B Preferred Stock of the Company (the "Series B Preferred Stock").

     B.  Pursuant to the Investors' Rights Agreement, the Company granted the
Investors certain registration rights, information rights and rights of first
offer in connection with the purchase and sale of Series B Preferred Stock.

     C.  The Company desires to sell up to 2,400,000 shares of Common Stock and
additional shares of Series B Preferred Stock (the "Additional Shares") to
certain Investors and in order to induce such Investors to purchase the
Additional Shares, the Company proposes amending relevant sections of the
Investors' Rights Agreement to provide such Investors with the same registration
rights, information rights and rights of first offer in connection with the
Additional Shares as granted pursuant to the Investors' Rights Agreement.

     NOW, THEREFORE, in consideration of the mutual promises and covenants set
forth herein, and for other consideration, the receipt and adequacy of which is
hereby acknowledged, the Company and the Investors hereby agree as follows
effective upon the second closing of the Series B Preferred Stock Financing:

     1.   Section 1.1(g) of the Investors' Rights Agreement is hereby amended to
read in its entirety as follows:

          "(g)   "Registrable Securities" shall mean (i) shares of Common Stock
     issued to Series A Shareholders or Series B Investors or issued or issuable
     pursuant to the conversion of the Shares; (ii) any Common Stock issued as a
     dividend or other distribution with respect to or in exchange for or in
     replacement of the shares referenced in (i) above, provided, however, that
     Registrable Securities shall not include any shares of Common Stock which
     have previously 

                                      -1-
<PAGE>
 
     been registered or which have been sold to the public; (iii) 2,400,000
     shares of Common Stock issued to U.S. West Communications Services, Inc.;
     and (iv) solely for the purposes of Section 1.3 hereof, Registrable
     Securities shall be deemed to include shares of Common Stock of the Company
     held by David Hayden, Peter Flaxman, Wayne Correia and Marcy Swenson
     ("Founders Stock")."

     2.   The first paragraph of Section 1.2(a) is hereby amended to read in its
entirety as follows:

          "(a)  Request for Registration.  If the Company shall receive from
     Initiating Holders at any time or times not earlier than the earlier of (a)
     March 31, 2002 or (b) six (6) months after the effective date of the first
     registration statement filed by the Company covering an underwritten
     offering of any of its securities to the general public, a written request
     that the Company effect any registration with respect to all or a part of
     the Registrable Securities having an aggregate offering price, net of
     underwriting discounts and expenses, the anticipated gross proceeds of
     which (prior to deduction for underwriter's discounts and expenses related
     to the issuance) exceed $12,500,000 and an initial offering price of at
     least $1.312 per share (as adjusted for any combinations, consolidations,
     subdivisions, splits or stock dividends with respect to such shares of
     Common Stock) the Company will:"

     3.   Section 1.2(a)(ii)(B) of the Investors' Rights Agreement is hereby
amended to read in its entirety as follows:

          "(B)  After the Company has initiated two such registrations pursuant
     to this Section 1.2(a) (counting for these purposes only registrations
     which have been declared or ordered effective and pursuant to which not
     less than 80% of the Registrable Securities included therein have been sold
     and registrations which have been withdrawn by the Holders as to which the
     Holders have not elected to bear the Registration Expenses pursuant to
     Section 1.4 hereof and would, absent such election, have been required to
     bear such expenses);"

     4.   Section 1.6(a) is hereby amended in its entirety to read as follows:

          "(a)  Keep such registration effective for a period of one hundred
     twenty (120) consecutive days or until the Holder or Holders have completed
     the distribution described in the registration statement relating thereto,
     whichever first occurs; provided, however, that a. such one hundred twenty
     (120) consecutive day period shall be extended for a period of time equal
     to the period the Holder refrains from selling any securities included in
     such registration at the request of an underwriter of Common Stock (or
     other securities) of the Company; and b. in the case of any registration of
     Registrable Securities on Form S-3 which are intended to be offered on a
     continuous or delayed basis, such one hundred twenty (120) day consecutive
     period shall be extended, if necessary, to keep the registration statement
     effective until all such Registrable Securities are sold, provided that
     Rule 415, or any successor rule under the Securities Act, permits an
     offering on a continuous or delayed basis, and provided further that
     applicable

                                      -2-
<PAGE>
 
     rules under the Securities Act governing the obligation to file a post-
     effective amendment permit, in lieu of filing a post-effective amendment
     that i. includes any prospectus required by Section 10(a)(3) of the
     Securities Act or ii. reflects facts or events representing a material or
     fundamental change in the information set forth in the registration
     statement, the incorporation by reference of information required to be
     included in (A) and (B) above to be contained in periodic reports filed
     pursuant to Section 13 or 15(d) of the Exchange Act in the registration
     statement;"

     5.   Section 1.14 of the Investors' Rights Agreement is hereby amended in
its entirety as follows:

          "1.14  Termination of Registration Rights.  The right of any Holder to
     request registration or inclusion in any registration pursuant to Section
     1.2, 1.3 or 1.5 shall terminate after the earlier of (i) five (5) years
     following the closing of the initial public offering of Common Stock of the
     Company, or (ii) at such time, following a public offering that meets the
     requirements necessary to trigger an automatic conversion of Preferred
     Stock under the Company's Articles of Incorporation, as amended to date, as
     Rule 144 or another similar exemption under the Securities Act is available
     for the sale of all of such Holder's shares during any ninety (90) day
     period; provided, however, that this clause (ii) shall not apply to a
     Holder of greater than 5% of the Company's Common Stock."

     6.   Section 2.6 of the Investors' Rights Agreement is hereby amended in
its entirety as follows:

          "2.6  Termination of Covenants.  The covenants set forth in Sections
     2.1, 2.2, 2.3, 2.4 and 2.5 shall terminate and be of no further force or
     effect (a) when the sale of securities pursuant to a registration statement
     filed by the Company under the Securities Act in connection with the firm
     commitment underwritten offering of its securities to the general public is
     consummated, the aggregate gross proceeds of which (prior to deduction for
     underwriter's discounts and expenses related to the issuance) exceed
     $30,000,000 and an initial offering price of at least $7.7492 per share (as
     adjusted for any combinations, consolidations, subdivisions, splits or
     stock dividends with respect to such shares of Common Stock), or (b) when
     the Company first becomes subject to the periodic reporting requirements of
     Sections 13 or 15(d) of the Exchange Act, whichever event shall first
     occur."

     7.   Section 3.1 of the Investors' Rights Agreement is hereby amended in
its entirety as follows:

          "3.1  Waiver of Right of First Offer.  Each Series A Shareholder and
     Founder holding a right of first offer to purchase new securities of the
     Company pursuant to Section 2.3 of the Original Rights Agreement and each
     Series B Investor holding a right of first offer to purchase new securities
     of the Company pursuant to Section 2.3 of this Agreement, by its execution
     of this Agreement, hereby waives any rights it may have pursuant to such
     section to purchase a greater number of shares of Series B Preferred Stock
     than the number such 

                                      -3-
<PAGE>
 
     Investor is purchasing under the Purchase Agreement."

     8.   Except as expressly modified herein, the Investors' Rights Agreement
shall remain in full force and effect.

     This Amendment to the Amended and Restated Investors' Rights Agreement may
be executed in any number of counterparts, each of which shall be an original,
but all of which together shall constitute one and the same instrument.


                                   COMPANY
                              

                                   CRITICAL PATH, INC., a California corporation



                                   By /s/ Douglas Hickey
                                      ------------------------------------------
                                                   Douglas Hickey
                                         President and Chief Executive Officer

                                      -4-
<PAGE>
 
                                   INVESTORS


                                   E*TRADE Group, Inc.



                                   By /s/
                                      ------------------------------------------

                                   Title  CFO
                                         ---------------------------------------


                                   BENCHMARK CAPITAL PARTNERS II, L.P.
                                   as nominee for
                                   Benchmark Capital Partners II, L.P.,
                                   Benchmark Founders Fund II, L.P.,
                                   Benchmark Founders Fund II-A, L.P. and
                                   Benchmark Members' Fund II, L.P.

                                   By   Benchmark Capital Management Co. II,
                                   L.L.C., general partner



                                   By /s/ 
                                      ------------------------------------------
                                                   Managing Member



                                   US WEST DATA INVESTMENTS, INC.



                                   By /s/
                                      ------------------------------------------

                                   Title
                                         ---------------------------------------


                                   HAMBRECHT & QUIST CALIFORNIA



                                   By
                                      ------------------------------------------

                                   Title
                                         ---------------------------------------


                     Signature Page to Critical Path, Inc.
         Amendment to Amended and Restated Investors' Rights Agreement

                                      -5-
<PAGE>
 
                                   H&Q CRITICAL PATH INVESTORS, L.P.



                                   By
                                      ------------------------------------------

                                   Title
                                         ---------------------------------------


                                   HAMBRECHT & QUIST EMPLOYEE VENTURE FUND, L.P.



                                   By
                                      ------------------------------------------

                                   Title
                                         ---------------------------------------


                                   CMG@VENTURES II, L.L.C.



                                   By /s/ 
                                      ------------------------------------------

                                   Title
                                         ---------------------------------------


                                   ATTRACTOR LP



                                   By /s/ Harvey Allison, MM
                                      ------------------------------------------
                                   Title Attractor Ventures LLC, GP 
                                         ---------------------------------------
                                         Attractor LP


                                   ATTRACTOR DEARBORN PARTNERS LP



                                   By /s/ Harvey Allison, MM
                                      ------------------------------------------
                                   Title Attractor Ventures LLC, GP 
                                         ---------------------------------------
                                         Attractor LP

                     Signature Page to Critical Path, Inc.
         Amendment to Amended and Restated Investors' Rights Agreement

                                      -6-
<PAGE>
 
                                   ATTRACTOR INSTITUTIONAL



                                   By /s/ Harvey Allison, MM
                                      ------------------------------------------
                                   Title Attractor Ventures LLC, GP 
                                         ---------------------------------------
                                         Attractor LP


                                   NETWORK SOLUTIONS, INC.



                                   By /s/
                                      ------------------------------------------

                                   Title CFO and Acting COO
                                         ---------------------------------------


                                   MOHR, DAVIDOW VENTURES V, L.P.

                                   By  Fifth MDV Partners, L.L.C.



                                   By /s/ George Zachary
                                      ------------------------------------------
                                                   Managing Member              



                                   MOHR, DAVIDOW VENTURES V, L.P., as nominee
                                   for MDV Entrepreneurs' Network Fund II(A),
                                   L.P. and MDV Entrepreneurs' Network Fund
                                   II(B), L.P.


                                   By  Fifth MDV Partners, L.L.C.



                                   By /s/ George Zachary
                                      ------------------------------------------
                                                   Managing Member              

                     Signature Page to Critical Path, Inc.
         Amendment to Amended and Restated Investors' Rights Agreement

                                      -7-
<PAGE>
 
                                   THE LEVINSON FAMILY TRUST, KATHY LEVINSON AND
                                   JENNIFER LEVINSON, TRUSTEES, UAD 1/17/94



                                   By  /s/
                                      ------------------------------------------

                                   Title  Trustee 
                                         ---------------------------------------


                                    /s/ Jerry Gramaglia
                                   ---------------------------------------------
                                                 Jerry Gramaglia



                                   THE LEONARD C. PURKIS REVOCABLE TRUST, UAD
                                   4/24/97



                                   By  /s/
                                      ------------------------------------------

                                   Title  Trustee
                                         ---------------------------------------


                                    /s/ Debra J. Chrapaty
                                   ---------------------------------------------
                                                 Debra J. Chrapaty



                                   RAMSEY/BEIRNE INVESTMENT POOL II, L.L.C.



                                   By  /s/
                                      ------------------------------------------

                                   Title  Member/CFO  
                                         ---------------------------------------


                                   THE COTSAKOS REVOCABLE TRUST, UAD 9/3/87



                                   By
                                      ------------------------------------------

                     Signature Page to Critical Path, Inc.
         Amendment to Amended and Restated Investors' Rights Agreement

                                      -8-
<PAGE>
 
                                   SOFTBANK TECHNOLOGY VENTURES



                                   By  /s/ Gary E. Rieschel
                                      ------------------------------------------

                                   Title   Managing General Partner
                                         ---------------------------------------


                                   SOFTBANK TECHNOLOGY ADVISORS FUND



                                   By  /s/ Gary E. Rieschel
                                      ------------------------------------------

                                   Title   Managing General Partner
                                         ---------------------------------------


                                   DIGITAL MEDIA CAPITAL, LLC



                                   By  /s/ Erin W. Jansen
                                      ------------------------------------------

                                   Title   Cheif Operating Officer
                                         ---------------------------------------


                                        /s/ John A. Axel
                                   ---------------------------------------------
                                                   John A. Axel


                                        /s/ Randy Borden
                                   ---------------------------------------------
                                                    Randy Borden


                                        /s/ John Dunning
                                   ---------------------------------------------
                                                   John Dunning


                                        /s/ Lori Fena
                                   ---------------------------------------------

                     Signature Path to Critical Path, Inc.
         Amendment to Amended and Restated Investors' Right Agreement

                                      -9-
<PAGE>
 
                                                   Lori K. Fena


                                        /s/ Mitchell Fong
                                   ---------------------------------------------
                                                  Mitchell Fong

                                   
                                        /s/ Lisa Gansky
                                   ---------------------------------------------
                                                  Lisa Gansky


                                        /s/ Hillary Hayden 
                                   ---------------------------------------------
                                                   Hillary Hayden 


                                        /s/ Storey Jones 
                                   ---------------------------------------------
                                                    Storey Jones 


                                        /s/ Brian Kambe 
                                   ---------------------------------------------
                                                    Brian Kambe 


                                        /s/ Charles Larkin, Jr. 
                                   ---------------------------------------------
                                                 Charles Larkin, Jr. 



                                   ---------------------------------------------
                                                   Marian Larkin



                                   ---------------------------------------------
                                                 Giles W. McNamee


                                        /s/ Ullas J. Naik 
                                   ---------------------------------------------
                                                   Ullas J. Naik 

                     Signature Page to Critical Path, Inc.
         Amendment to Amended and Restated Investors' Rights Agreement

 

                                      -10-
<PAGE>
 
                                             /s/ Minturn S. Osborne
                                   ---------------------------------------------
                                                  Minturn S. Osborne


                                             /s/ Joseph C. Pistritto
                                   ---------------------------------------------
                                                Joseph C. Pistritto


                                             /s/ Ram Shriram
                                   ---------------------------------------------
                                                    Ram Shriram



                                   S.D. LIVING TRUST, ALBERT W. SMITH, TRUSTEE
                                             
                                             S.D. Living Trust

                                   By  /s/ Albert W. Smith Trustee 
                                      ------------------------------------------


                                             /s/ Charles Swenson
                                   ---------------------------------------------
                                                  Charles Swenson


                                             /s/ Jorge del Calvo
                                   ---------------------------------------------
                                                  Jorge del Calvo


                                             /s/ Stanley F. Pierson
                                   ---------------------------------------------
                                                 Stanley F. Pierson


                                             /s/ David Hayden
                                   ---------------------------------------------
                                                    David Hayden

                     Signature Page to Critical Path, Inc.
         Amendment to Amended and Restated Investors' Rights Agreement

                                      -11-
<PAGE>
 
                                   PETER FLAXMAN & CATHERINE FLAXMAN, TRUSTEES,
                                   THE FLAXMAN 1992 REVOCABLE CHILDREN'S TRUST



                                   By
                                      ------------------------------------------
                                                 Peter Flaxman, Trustee


                                   By
                                      ------------------------------------------
                                              Catherine Flaxman, Trustee


                                        
                                        /s/ Wayne Correia 
                                   ---------------------------------------------
                                                  Wayne Correia 



 
                                   ---------------------------------------------
                                                  Marcy Swenson



                                        /s/ Charles L. Larkin
                                   ---------------------------------------------
                                          Charles L. Larkin III, Custodian
                                               FBO Charles Larkin IV

          
                                        /s/ Charles L. Larkin
                                   ---------------------------------------------
                                          Charles L. Larkin III, Custodian
                                                FBO Diana M. Larkin



                                   ---------------------------------------------
                                            David S. Larkin, Custodian
                                              FBO Matthiah M. Larkin

                     Signature Page to Critical Path, Inc.
         Amendment to Amended and Restated Investors' Rights Agreement

                                      -12-
<PAGE>
 
                                   ---------------------------------------------
                                             David S. Larkin, Custodian
                                                FBO Phoebe E. Larkin



                                   ---------------------------------------------
                                                   Sarah M. Larkin
  
                     Signature Page to Critical Path, Inc.
         Amendment to Amended and Restated Investors' Rights Agreement

                                      -13-
<PAGE>
 
                                   EXHIBIT B
       

                             SERIES A SHAREHOLDERS



                               Benchmark Capital
                            Mohr, Davidow Ventures
                            CMG@Ventures II, L.L.C.
                         Softbank Technology Ventures
                       Softbank Technology Advisors Fund
                              E*TRADE Group, Inc.
                          Digital Media Capital, LLC
                                 David Hayden
                                 John Dunning
                                 Mitchell Fong
                                  Lisa Gansky
                                 Storey Jones
                              Charles Larkin, Jr.
                                 Marian Larkin
                                  Ram Shriram
                              S.D. Living Trust,
                           Albert W. Smith, Trustee
                                  Brian Kambe
                               Howard T. Larkin
                                 John A. Axel
                                 Randy Borden
                                Hillary Hayden
                               Giles W. McNamee
                              Minturn S. Osborne
                              Joseph C. Pistritto
                                 Lori K. Fena
                                 Ullas J. Naik
                                Charles Swenson
                                Jorge del Calvo
                              Stanley F. Pierson
 
                                     SA-1
<PAGE>
 
                                   EXHIBIT A


                               LIST OF INVESTORS


                                     SB-1
<PAGE>
 
                                   EXHIBIT C


                               LIST OF FOUNDERS



                                 David Hayden
                                 Peter Flaxman
                                 Wayne Correia
                                 Marcy Swenson


                                     SC-1
