Bereits 1988 jammen Douglas McCombs (Bass, Gitarre) und John Herndon (Drums,Sequenzer) zusammen bei einigen Sessions. Beide verbindet ihr Interesse für ausgefallene Rhythmik und progressive Musik. Kurze Zeit später gründen sie dann mit John McEntire (Drums, Gitarre, Synthesizer), Bundy K. Brown (Bass) und Gitarrist David Pajo Tortoise. Die Musik der Chicagoer Instrumental-Band wird gerne als Postrock bezeichnet. Die Band wehrt sich allerdings gegen derartige Genrebezeichnungen hartnäckig. Nach ihrem Empfinden spielen sie einfach nur „Musik“ Tortoise collagenartiger Umgang mit Elementen aus Dub, Minimal, elektronischer Musik und Jazz gründet in weiten Teilen in der Experimentierfreudigkeit des Krautrock.

Ein Jahr nachdem ihr Erstlingswerk „Tortoise“ (1994) erschienen war, veröffentlichten Tortoise ein Remixalbum namens „Rhythms, Resolutions and Clusters“. Bassist Brown verließ kurz darauf die Band. Ihre ersten großen Ausrufezeichen setzte die Band mit den Alben „Millions Now Living Will Never Die“(1996) und „TNT“(1998). Schnell wurden sie zu Lieblingen der Fachpresse und gingen auf große Europa Tournee. Weil er anderen musikalischen Projekten nachgehen wollte, verließ Gitarrist Pajo die Band 1998. Das drei Jahre später heraus gebrachte „Standards“ birgt keineswegs Standards im eigentlichen Sinn, sondern eine Reihe von äußerst experimentellen Stücken der Band.
Ebenfalls erwähnenswert sind die Alben „It’s All Around You“(2004) und das Cover-Album „The Brave and the Bold“(2006), welches zusammen mit Bonnie „Prince“ Billy aufgenommen wurde.

Robert Schwabe