: Spine and Sensory, grabado por Tim Green en su estudio "Louder Studios" en San Francisco, el álbum fue distribuido por Makoto Recordings en abril de 1999, este año también lanzaron "Insound Tour-support Series Vol.
En abril del año [2000] grabaron su segundo álbum Dream Signals in Full Circles con el productor Dave Trumfio en su estudio King Size Sound Labs en Chicago; el álbum fue distribuido por Tiger Style Records en septiembre de este año, el álbum fue muy bien recibido en todo el mundo con lo que a principios del 2001 Tristeza salió de gira a Europa y Japón por primera vez.
Japón y Europa para promocionar estos lanzamientos; antes de esta gira Stephen Swesey salió de la banda y fue sustituido para la gira por Eric Hinojosa; desde entonces Swesey toca esporádicamente con el dúo electrónico Languis.
A principios del 2003 James LaValle toco por última vez con Tristeza para dedicarse de lleno a su proyecto The Album Leaf, así el grupo decidió tomarse un tiempo para descansar y buscar sustitutos para los dos miembros que salieron.
Este año la banda decidió lanzar un 12" en Gravity titulado Espuma que contiene canciones que no habían salido en discos anteriores y material en vivo, además de la primera canción de la banda sin LaValle titulada "This Trap".