Gates tocó con muchas bandas en sus años de formación, estableciendo relaciones que informarían toda su carrera musical. Algunos de sus primeros proyectos fueron Town Number Eight (con el compositor Derek Greenberg) y varias bandas de hardcore punk rock que estaban fuertemente influenciadas por el sonido LA Hardcore.
En 1981, Gates cantó y tocó el bajo para Monkey Rhythm, una banda que comenzó (con el guitarrista británico Graham Clarke y el baterista Chuck Risby) mientras asistía a Miramonte High School en Orinda California. Con las referencias musicales de la banda claramente en desacuerdo con los gustos musicales suburbanos locales, Monkey Rhythm se aventuró en el circuito de clubes de San Francisco, tocando en numerosos espectáculos en The Mabuhay Gardens, On Broadway, The Stone, Berkeley Square y muchos otros. La banda realizó giras constantemente (a nivel nacional con The Fine Young Cannibals, entre otros) hasta asegurar un contrato discográfico con 415/CBS Music de Howie Klien. Su álbum debut "This Must Be The Place" (producido por Matt Wallace) fue lanzado en 1985.
En 1987, la banda original se disolvió y Gates, manteniendo el nombre de Monkey Rhythm, tocó con varios músicos locales y amigos (Wire Trains Jeff Trott y Brian McCloud) mientras continuaba estudiando Diseño Gráfico en San Francisco State.
Mientras escribía música de manera intermitente con el teclista John Berg (quien tocó brevemente en Monkey Rhythm), Gates comenzó a trabajar con el multiinstrumentista Matt Winegar (quien llamó la atención de Gates después de que su amigo Les Claypool lo recomendara). Gates y Winegar desarrollaron una fructífera relación de trabajo, que los tuvo aislados en la casa de Winegars en Fremont CA durante meses, grabando en una primitiva Tascam 388. La pareja musical desarrolló lentamente su estilo pop melódico mientras acumulaba una gran colección de canciones originales. Con la ayuda de Matt Wallace, el dúo (con el teclista John Berg) consiguió un contrato editorial con el gigante editorial Peer Music.
Mientras todavía usaban tentativamente el nombre Monkey Rhythm, Gates, Berg y Winegar crearon una banda en vivo (con el baterista Mike Urbano y el bajista y viejo amigo Derek Greenberg en el bajo). La banda pronto generó interés de varios sellos hasta firmar con Geffen Records. La banda poco después cambió su nombre a "The Spent Poets".
The Spent Poets grabaron su álbum debut para Geffen y luego realizaron una gira nacional con la banda Live.