La banda se formó en septiembre de 1968 por el baterista Jon Hiseman, el saxo tenor Dick Heckstall-Smith y el bajista Tony Reeves, que habían tocado juntos previamente en la banda de John Mayall, The Bluesbreakers. Dave Greenslade (órgano), se incoporó muy pronto, y el grupo se completó con Jim Roche en la guitarra, aunque apenas permaneció el tiempo justo para grabar algún corte, siendo reemplazado por James Litherland, (guitarra y cantante). Hiseman y Heckstall-Smith habían tocado también, antes, con la banda de Graham Bond, y colosseum utilizó algunos de los temas de éste periodo. La banda hizo su debut en Newcastle y consiguieron rápidamente aparecer en el programa del DJ John Peel, Top Gear (BBC Radio 1).

Su primer álbum, Those Who Are About To Die Salute You, fue publicado por Fontana en 1969, y en marzo de ese mismo año, aparecieron en Supershow, grabación de una jam session con Modern Jazz Quartet, Led Zeppelin, Jack Bruce, el Roland Kirk Quartet, Eric Clapton, Stephen Stills, y Juicy Lucy. Su segundo disco, también de 1969, fue Valentyne Suite, primero publicado por Vertigo Records, una división de Philips Records dirigida a publicar a grupos aún no muy conocidos, y que había publicado también a Black Sabbath.

Para el tercer álbum, The Grass Is Greener, publicado solamente en Estados Unidos, en 1970, Dave “Clem” Clempson reemplazó a James Litherland; Louis Cennamo había sustituido igualmente a Tony Reeves en el bajo, pero a su vez fue reemplazado por Mark Clarke sólo un mes más tarde, y Hiseman reclutó al vocalista Chris Farlowe para que Clempson se concentrara en la guitarra. Esta se suele considerar como la formación definitiva de Colosseum, y es la que aparece en el disco Daughter of Time (1970).

En marzo de 1971, grabó sus conciertos en el Big Apple Club de Brighton y en la Universidad de Manchester. Las grabaciones se publicaron en forma de doble álbum, Colosseum Live, en 1971. Tras la disolución de la banda, Jon Hiseman formó Tempest junto a Mark Clarke. Dave Greenslade formó Greenslade con Tony Reeves; Clem Clempson se unió a Humble Pie; Chris Farlowe hizo lo mismo con Atomic Rooster; y Dick Heckstall-Smith inició una carrera en solitario.

Hiseman volvió a unir el grupo, con el nombre de Colosseum II, en 1975, con una orientación aún más decidida hacia el jazz fusión. Los ensayos iban a comenzar el 1 de enero de 1975, pero la formación no se terminó de concretar hasta mayo de ese mismo año. Entre los músicos que participaron en el nuevo el grupo estuvieron Graham Bell, Duncan Mackay y Clarke Mark. La formación se completó con Don Airey, Neil Murray, Gary Moore y Mike Starr. En esta etapa, la banda grabó y editó tres álbumes entre 1976 y 1978.

Colosseum se reunió otra vez en junio de 1994, tocando en el “Freiburg Zelt Musik Festival” y realizando un show de TV que se grabó y publicó como CD y DVD. Se realizaron algunas ediciones de nuevas grabaciones,3 además de realizar algunas re-ediciones ampliadas.

Barbara Thompson, saxofonista, flautista y clarinetista que es esposa de Hiseman y que había trabajado con Colosseum desde los primeros tiempos, se incorporó a la banda en varias ocasiones tras la muerte de Dick Heckstall-Smith, ocurrida en el 2004. Thompson permanecería como miembro estable.

Colosseum continúa grabando y dando actuaciones en clubs.

Primer periodo
Those Who Are About to Die Salute You – (1969)
Valentyne Suite – (1969)
The Grass Is Greener – (1970) (sólo en EEUU)
Daughter of Time – (1970)
Colosseum Live – (1971)

Como Colosseum II
Strange New Flesh – (1976)
Electric Savage – (1977)
War Dance – (1977)

Periodo final
Lives: The Reunion Concerts 1994 – (1995)
Bread & Circuses – (1997)
Tomorrow’s Blues – (2003)
Live Cologne 1994 – (2003)
Live 05 – (2007)
Time On Our Side – (2014)

Recopilatorios
The Collectors Colosseum – (1971)
Anthology – (2000) (2-CD)
Morituri Te Salutant – (2009) (4-CD)