Formé à Plymouth, dans le Minnesota, le groupe attire l'intérêt en 1996 en remportant un concours national, sponsorisé par Sam Goody[3]. Warne nomme le groupe d'après la phrase ace troubleshooter, qu'il a lu dans un livre[4].
La formation d'Ace Troubleshooter change à plusieurs reprises, se lançant à l'origine comme trio : John Warne, Josh Abbott et Matt Pacyga. Ils recrutent Isaac Deaton comme second guitariste en 1998. Nombre de bassistes et guitaristes passeront au sein du groupe. Seuls deux des premiers membres, John Warne et Josh Abbott, y reste jusqu'à la fin. Tous deux ont joué au sein de Guerilla Rodeo peu avant la dissolution d'Ace.
Le groupe Relient K et Ace ont tourné ensemble. Le batteur Dave Douglas, membre de tournée pour Relient K, devient leur guitariste pendant une courte durée. Warne deviendra bassiste pour Relient K après le départ de Brian Pittman. Matt Thiessen de Relient K explique en 2000 qu'Ace leur permettaient de vivre dans leur bus, Relient K ayant à peine commencé[5].
En février 2005, Toby David annonce la séparation du groupe sur un forum[6]. Warne part jouer de la basse pour Relient K. Abbott rejoindra My Red Hot Nightmare.
