Google dimulai sebagai sebuah proyek pencarian pada Januari 1996 oleh Larry Page dan Sergey Brin, dua mahasiswa Ph. D. di Universitas Stanford, California.[5] Mereka menghipotesiskan bahwa sebuah mesin pencari yang menganalisa pereratan antara website dapat menghasilkan hasil yang lebih baik daripada teknik yang sudah ada, yang menilai hasil berdasarkan jumlah pencarian tersebut muncul pada sebuah halaman.[6] Mesin pencari mereka disebut "BackRub" karena pranala kembali sistemnya dapat memperkirakan pentingya sebuah situs.[7] Sebuah mesin pencari kecil bernama Rankdex telah menggunakan strategi yang sama.[8] Diyakini bahwa halaman dengan pranala lebih banyak dari halaman web yang relevan merupakan halaman paling relevan yang dikaitkan dengan pencarian, Page dan Brin menguji tesis mereka sebagai bagian dari pembelajaran mereka, dan mendirikan tumpuan untuk mesin pencari mereka. Aslinya, mesin pencari tersebut menggunakan website Universitas Stanford dengan domain google.stanford.edu. Domain google.com diregistrasikan tanggal 15 September 1997,[9] dan perusahaan ini berdiri dengan nama Google Inc. tanggal 7 September 1998 pada sebuah garasi rumah di Menlo Park, California. Investasi awal yang diperoleh untuk perusahaan baru ini bernilai hampir $1,1 juta, termasuk sebuah cek senilai $100.000 dari Andy Bechtolsheim, salah seorang pendiri Sun Microsystems.[10]
Bulan Maret 1998, perusahaan ini memindahkan kantornya ke Palo Alto, rumah bagi beberapa perusahaan teknologi di Silicon Valley.[11] Setelah tumbuh melampaui dua situs lainnya, perusahaan ini menyewa sebuah komplek bangunan di 1600 Ampitheatre Parkway, Mountain View dari Silicon Graphics (SGI) pada tahun 2003.[12] Google telah menetap di lokasi itu hingga saat ini, dan komplek ini mulai dikenal sebagai Googleplex (plesetan dari kata googolplex, angka 1 yang diikuti oleh seratus nol). Tahun 2006, Google membeli properti dari SGI sebesar $319 juta.[13]
Mesin pencari Google menarik perhatian jumlah pengguna Internet yang terus meningkat, yang menyukai desain sederhana dan penggunaannya.[14] Pada tahun 2000, Google mulai menjual iklan yang dikaitkan dengan kata kunci pencarian. Iklan tersebut hanya berupa teks polos untuk menjaga sebuah desain halaman yang teratur dan untuk meningkatkan kecepatan pemunculan halaman.[5] Kata kunci dijual berdasarkan pada kombinasi tawaran harga dan jumlah klik, dengan penawaran dimulai pada 5 sen (US$) per klik.[5] Model penjualan iklan kata kunci dirintis oleh Goto.com (akhirnya mengubah nama menjadi Overture Services, sebelum diambil alih oleh Yahoo! dan diganti merek menjadi Yahoo! Search Marketing).[15][16][17] Sementara berbagai pesaing dot-comnya gagal dalam pasaran Internet baru, Google memperkuat pengaruhnya untuk meningkatkan pendapatan.[5]
Nama "Google" berasal dari ucapan "googol"[18][19] yang salah, yang merujuk pada 10100 (angka yang itunjukkan oleh 1 yang diikuti oleh seratus nol). Setelah kata ini menjadi ucapan sehari-hari, kata "google", dimasukkan dalam Merriam Webster Collegiate Dictionary dan Oxford English Dictionary pada 2006, yang berarti "menggunakan mesin pencari Google untuk memperoleh informasi di Internet."[20][21]
Sebuah paten yang menggambarkan bagian dari mekanisme penilaian Google (Page Rank) disetujui pada 4 September 2001.[22] Paten ini secara resmi ditetapkan oleh Universitas Stanford dan memasukkan nama Lawrence Page sebagai sang pencipta.