Nem mondhatni, hogy túlságosan jó viszonyba kerültek volna, eleinte ugyanis szinte minden témában ellenkező véleményt vallottak. Egyetlen dologban értettek egyet: valami olyan adatbázison kezdtek el közösen munkálkodni, ami a világ legtöbb és legfontosabb információt gyűjti össze.
1996 januárjában döntöttek úgy, hogy belefognak egy keresőmotor kifejlesztésébe, melyet BlackRubnak neveztek el, mert arra tervezték, hogy felismerje a "fekete linkeket" egy adott weboldalon. Larry volt kettőjük közül az, aki mindig is szeretett kísérletezgetni, bütykölni. Ő hozta létre azt a szerverkörnyezetet, amely viszonylag olcsó számítógépeket használ, nincs szüksége drága berendezésekre a kiszolgáláshoz. Közben a BlackRub motor egyre csak fejlődött, formálódott.
1998-ra mintegy 1 terabájtnyi merevlemez-kapacitást vásároltak és Larry lakóházában berendeztek egy szobát a szervereknek, így létrejött a világ legelső adatközpontja. Eközben Sergey bérbe vett egy irodahelyiséget, és megkezdték a potenciális partnerek felkutatását, akik hajlandóak lennének licensz jogokat vásárolni a kereső technológiájukra. A felhívottak között főleg barátok voltak, de megkeresték a Yahoo! alapítóját, David Filót is, aki elismerte a két lelkes fiatal munkáját, de annyit mondott, térjenek vissza akkor a témára, amikor szerzeményüket teljesen kifejlesztették.
Végül úgy döntöttek, radikálisabb lépésekre szánják el magukat. Pénzt kellett szerezniük, hogy kiköltöztethessék a szervereket. Írtak hát egy üzleti tervet és befektetők után kezdtek el keresgélni. Andy Bechtolsheim, a Sun Microsystems társalapítója volt az elsők egyike, aki részese lehetett a bemutatónak, amely annyira meggyőzte őt, hogy gyorsan ki is állított egy százezer dolláros csekket, hogy a fiatalok megalapíthassanak egy céget, amelynek a Google Inc. nevet adták. Ez persze nem volt elég, kisebb-nagyobb nehézségek árán egymilliót gyűjtöttek össze.
Innentől aztán beindult a szekér, egyre több cég érdeklődött a szolgáltatás iránt, és még 1998 végén beindult a Google kereső béta verziója, amely ekkor mindössze 10 ezer oldal között volt képes adatokat keresni. Ez a szám hónapról hónapra, sőt napról napra emelkedett. Mára közel tízmilliárdra tehető az adatbázisban található oldalak száma, bár ezt az elmúlt hónapok óta már nem jelenítik meg a kereső főoldalán - miután a konkurens Yahoo! egy jóval nagyobb adatot tett közzé.
