1996年1月、スタンフォード大学の博士課程に在籍するラリー・ペイジとセルゲイ・ブリンによる研究プロジェクトとしてGoogleの歴史は始まった[17]。ラリー・ペイジ（左）とセルゲイ・ブリン（右）、2003年
当時の検索エンジンは、検索されたキーワードがそのウェブページに登場する回数によって各ページをランクづけし、検索結果として表示していた。ペイジとブリンは、ウェブサイト同士の関係を分析することで検索結果をランクづけする、改良された検索エンジンの理論を提唱した[18]。ペイジとブリンが理論化した新しい検索エンジンは、検索におけるウェブサイトの適合性を判断するにあたって、そのサイトへのリンクを貼っているウェブページの数と、それらのウェブページの重要度（品質）の2つを評価するものだった。2人はこの新技術を「PageRank（ページランク）」と名づけた[19][20]。
ペイジとブリンによる新しい検索エンジンは、ウェブサイトの重要度を被リンク（バックリンク）の数をチェックすることで評価したため、当初2人はこの検索エンジンを「BackRub（バックラブ、背中へのマッサージの意）」とのニックネームで呼んでいた[21][22][23]。（このエピソードにちなんだ社名の会社も存在する。[24]）最終的に、この検索エンジンは「Google」と名付けられたが、これは「googol（グーゴル）」という数の単位の綴り間違いに由来していた[25][26]。1グーゴルは1の後に0が100個連なった値であり、莫大な情報量を提供する検索エンジンであると示すための命名であった[27]。当初のGoogleのドメインは google.stanford.edu[28] および z.stanford.edu[29] であり、スタンフォード大学のウェブサイト下で運営されていた[30][31]。 1997年9月15日、Googleのためのドメイン名 google.com が登録された[32]。1998年9月4日、Googleは法人格を取得した。会社組織としてのGoogleの拠点は、カリフォルニア州メンローパークの、ペイジらの友人スーザン・ウォシッキーが所有するガレージに置かれた[17]。スタンフォード大学の博士課程で2人の同輩だったクレイグ・シルバースタイン
設立（1998年）
法人としての設立以前の1998年8月、Googleはサン・マイクロシステムズの共同創業者アンディ・ベクトルシャイムから10万ドルの出資を受けた[35]。1998年には、別の3人のエンジェル投資家（Amazon.com創業者ジェフ・ベゾス、スタンフォード大学計算機科学教授デビッド・チェリトン、起業家ラム・シュリラムの3人）もGoogleへの出資を行った[36]。1998年末から1999年初めにかけ、Googleはいくつかの少額の出資を受けた[36]。1999年3月、Googleは本社をカリフォルニア州パロアルトに移転した[37]。パロアルトには他にもいくつかの著名なシリコンバレーのスタートアップ企業が本拠を置いていた[38]。1999年6月7日、Googleが新たに2,500万ドルの資金調達に成功したことが発表された[39]。主な出資者には、ベンチャーキャピタルのクライナー・パーキンス・コーフィールド・アンド・バイヤーズとセコイア・キャピタルが含まれていた[35]。
1999年の初め、ブリンとペイジはGoogleをExciteに売り渡すことを希望していた。2人はExciteの最高経営責任者（CEO）ジョージ・ベルを訪問し、Googleを100万ドルで買収するオファーを持ちかけたが、ベルはこのオファーを拒絶した。 Exciteのベンチャーキャピタリストの1人ビノッド・コースラは、Googleを75万ドルで売り渡すようペイジらを説得することに成功したが、それでもベルはGoogle買収を却下した[40]。
当初、ペイジとブリンは「広告収入に頼る検索エンジン」に反対する姿勢を示していたが、2000年にGoogleは検索されたキーワードと関係のある広告を表示するサービスを開始した[17][41]。整然としたページデザインを維持するため、表示されるのはテキストベースの広告のみとされた[42]。
検索キーワードに応じた広告を表示し、広告収入を得るというビジネスモデルを最初に開拓したのは、ビル・T・グロス（英語版）が設立したGoTo.comだった[43][44]。GoTo.comの後身であるOverture Services社は、同社が保有するペイ・パー・クリック技術ならびに各キーワードごとに広告をオークション形式で販売する技法について、Googleが特許を侵害しているとして訴訟を起こした。