Mycobacterium bovis (M. bovis) causes major economy and public health problem in numerous countries. In Great Britain, despite the use of a test-and-slaughter strategy, the incidence of bovine tuberculosis (bTB) in cattle has steadily risen in recent years. One strategy being considered to reduce the burden of bTB in cattle is the development of an efficient vaccine. The only current potentially available vaccine against tuberculosis, live attenuated M. bovis bacille Calmette-Guérin (BCG), has demonstrated variable efficacy in both humans and cattle and the development of improved vaccination strategies for cattle is a research priority. In this study we assessed the immunogenicity in cattle of two recombinant BCG strains, namely BCG Pasteur Δzmp1::aph and BCG Danish Δzmp1. By applying a recently defined predictive immune-correlate of protection (T cell memory responses measured by cultured ELISPOT), we have compared these two recombinant BCG with wild-type BCG Danish SSI. Our results demonstrated that both strains induced superior T cell memory responses compared to wild-type BCG. These data provide support for the prioritisation of testing BCG Danish Δzmp1 in vaccination/M. bovis challenge studies to determine its protective efficacy.