According to Stanford's David Koller, and Google's own website, Page and Brin's 1996 foray into the world of search engines was initially called "BackRub."
Yes, BackRub.
They called it this because the program analyzed the web's "back links" to understand how important a website was, and what other sites it related to. BackRub operated on Stanford's servers until it eventually took up too much bandwidth.