La chiesa sorse, in Età Comunale sul luogo del martirio di Vitale ed Agricola, un servo e il suo padrone, i quali furono i primi martiri di Bologna, uccisi durante le persecuzioni decretate dall'imperatore Diocleziano alla fine del III secolo d.C. Essa venne chiamata dei Santi Vitale ed Agricola in Arena, in quanto, secondo la tradizione, in questo luogo sorgeva l'anfiteatro romano dove si esibivano i gladiatori e dove venivano eseguite le condanne dei cristiani.

La croce sulla quale sarebbe stato crocifisso Agricola è stata ritrovata ed è conservata nella chiesa dei santi Vitale e Agricola che fa parte del complesso Stefaniano. Sull'altare maggiore è presente una raffigurazione del martirio dei Ss. Vitale ed Agricola ad opera del pittore Busi.
Dell'antica chiesa romanica dedicata ai due martiri rimane soltanto l'antica cripta a tre navate.
Sulla facciata, sotto il portico in via S. Vitale, si trova la lapide del lettore dello studio bolognese Lucio de' Luzzi, che rappresenta il docente in cattedra di fronte ai discepoli e lo stemma della famiglia Luzzi (1318).