Rollins fue el cantante de los State of Alert (SOA) en Washington D. C. desde 1980 a 1981, tras lo cual cantó con los legendarios Black Flag, banda de hardcore punk californiano, desde agosto de 1981 hasta la disolución del grupo a principios de 1986. Black Flag no alcanzaron apenas difusión entre el gran público, pero a través de sus giras y actuaciones llegaron a ser considerados como uno de los grupos punk más importantes de la década de 1980.
Menos de un año después de la disolución de Black Flag, Rollins volvió a la música con su amigo de la adolescencia en Washington, el guitarrista Chris Haskett, el bajista Bernie Wandel y el batería Mick Green. Esta formación publicó dos grabaciones: Hot Animal Machine (acreditada como una grabación en solitario de Rollins, la portada incluye dibujos del líder de Devo, Mark Mothersbaugh) y Drive by Shooting (acreditada a «Henrieta Collins and the Wifebeating Childhaters»). La música era similar a la de Black Flag, aunque flirteando con el heavy metal y el jazz.
Poco después, Rollins fundó Rollins Band con Haskett, el bajista Andrew Weiss y el batería Sim Cain (estos dos habían tocado previamente con Gone, una banda de rock instrumental liderada por el guitarrista y fundador de Black Flag Greg Ginn).

El ingeniero de sonido Theo Van Rock fue habitualmente acreditado como un miembro más de la banda.
Weiss fue despedido tras la gira de End of Silence, siendo reemplazado por el bajista de jazz y funk Melvin Gibbs, que había sido encarecidamente recomendado por el guitarrista Vernon Reid. Tanto Gibbs como Cain, el batería, habían tocado en diferentes formaciones de la banda del guitarrista Marc Ribot.
Esta formación de la banda mostró las más abiertas influencias jazz de la historia de la banda: Gibbs había iniciado su carrera con la banda de jazz fusión del batería Ronald Shannon Jackson, y trabajó con Sonny Sharrock en álbumes como Seize The Rainbow (1987); Gibbs, junto a la obsesión de Rollins por la época del icónico trompetista Miles Davis de finales de la década de 1960 y principios de la de 1970, dieron forma a esta versión de la música de la banda. En esta época, Rollins Band grabó con el saxofonista de free jazz Charles Gayle, aunque dichas sesiones no se publicaron hasta pasados unos años.

El primer video procedente de Weight (1994), el esquizofrénico Liar, fue un gran éxito en MTV, con Rollins luciendo numerosos trajes (incluyendo uno de policía y uno de monja). La banda apareció en Woodstock 94, y Rollins fue invitado en muchos programas de la MTV, entre ellos, 120 Minutes.

Rollins Band firmó con la discográfica DreamWorks Records, con quien publicaron en 1997 Come In And Burn. El álbum no tuvo el éxito de Weight y, tras la gira, Rollins disolvió el grupo, arguyendo una sequía creativa.
Rollins reemplazó la formación Haskett-Gibbs-Cain con la banda de Los Ángeles Mother Superior, manteniendo el nombre Rollins Band, y publicó Get Some Go Again (2000) y Nice (2001). También publicaron un álbum doble en directo, The Only Way to Know for Sure. Esta fue una formación de un estilo arquetípicamente hard rock: su primer álbum incluía el tema "Are You Ready?", un cover de una canción del grupo Thin Lizzy, con la participación de su guitarrista Scott Gorham. Rollins ha expresado a menudo su debilidad por Thin Lizzy y su fundador, Phil Lynott.
En 2003 publicaron Rise Above: 24 Black Flag Songs to Benefit the West Memphis Three. El álbum incluye varios vocalistas invitados, incluyendo a Lemmy, Chuck D, Cedric Bixler-Zavala, Corey Taylor, Ice T, Tom Araya y otros, cantando canciones de Black Flag.
Entre otros compromisos, como su programa de radio Harmony In My Head, su programa de televisión The Henry Rollins Show, y sus giras de recitales hablados, Rollins volvió a reunir a Haskett, Gibbs y Cain, su segunda formación.
La banda abrió varios conciertos del grupo punk X, y actuaron en la final de la primera temporada de The Henry Rollins Show en agosto de 2006.