El álbum fue grabado durante una época tumultuosa en la formación de la banda. Varios miembros habían dejado la banda después de la grabación de Halfway between Here and There , aunque el ex saxofonista Noah Gaffney contribuyó en la canción "Anyone But You". El puesto de Gaffney finalmente fue ocupado por el saxofonista Steve Borth, ex miembro de la banda de ska-punk Link 80 de East Bay .
Después de la salida de James Salamone en el bajo, la banda tuvo muchos reemplazos temporales, incluido Johnny Tsagakis, el hermano menor del baterista Chris Tsagakis. Joe Troy, un viejo amigo de Embree que ayudó a escribir la canción "What If?", Finalmente se unió a la banda como bajista permanente.
Steve Choi, antes de The Chinkees , también se convirtió en miembro de pleno derecho tocando la guitarra y los teclados. Choi también había tocado teclados en las demos que la banda hizo para Progress , pero cuando llegó el momento de grabar, decidieron que Rich Zahniser de The Hippos tocara en el álbum, porque en ese momento estaba de gira con la banda. El ex trombonista de Jeffries Fan Club, Chris Colonnier, también tocó con la banda en ocasiones en el mismo papel que Zahniser. Progress ocupó el puesto 207 en los mejores álbumes de 2001.
Poco después del lanzamiento de Progress , Chris Sheets se unió como segundo trombón. Poco tiempo después, Rich Balling dejó la banda.
El álbum generó el primer video musical de la banda para la canción "Analog Boy". La banda no haría un segundo video musical por otros 5 años, hasta la canción principal de 2006's ... And the Battle Begun .