סרגיי ברין ולארי פייג’ הכירו במרץ 1995, במפגש הכוונה למועמדי דוקטורט במחשבים. פייג', שכבר היה שנתיים בתוכנית, נבחר להציג לסטודנטים, ביניהם ברין, את הקמפוס, ומשם השניים התיידדו.
באותו זמן פייג' הגה את רעיון ה-BackRub, זחלן אשר יעבור בין מיליוני מסמכים ברשת המקושרים ביניהם. מורכבותו וממדיו של הרעיון משכו את ברין לעבוד עם פייג'; לדבריו, "דיברתי עם הרבה קבוצות מחקר בקמפוס, וזה היה הפרויקט המעניין ביותר, גם מפני שהוא מנסה להתמודד עם גודלה של הרשת, שמסמלת את ידע האנושות, וגם מפני שחיבבתי את לארי".
כדי להפוך את הלינקים שזחלן ה-BackRub סיפק למדדים של חשיבות דפי אינטרנט, פיתחו ברין ופייג' את אלגוריתם הפייג' ראנק, במטרה לבנות מנוע חיפוש טוב יותר מכל מנוע אחר שהיה קיים בתקופתם. הוא התבסס על טכנולוגיה שניתחה את הרלוונטיות של הקישורים ההדדיים שמחברים דף אינטרנט למשנהו. באוגוסט 1996 הגרסה הראשונה של גוגל הייתה זמינה, אז רק ברשת האתרים של אוניברסיטת סטנפורד.
ב-1998, ברין ופייג' הקימו את חברת גוגל. פייג' שימש בתור נשיא-משנה של גוגל, ביחד עם ברין, עד 2001, אז הם שכרו את אריק שמידט בתור יושב ראש ומנכ"ל גוגל. השלושה ניהלו את גוגל כטריומווירט, עד ל-4 באפריל 2011, בו החליף פייג' את שמידט בתפקיד המנכ"ל, ושמידט מונה ליו"ר בפועל.