Ante-mortem bovine tuberculosis (bTB) tests for buffaloes include the single comparative intradermal tuberculin test (SCITT), interferon-gamma (IFN-γ) release assay (IGRA) and IFN-γ-inducible protein 10 release assay (IPRA). Although parallel test interpretation increases the detection of Mycobacterium bovis (M. bovis)-infected buffaloes, these algorithms may not be suitable for screening buffaloes in historically bTB-free herds. In this study, the specificities of three assays were determined using M. bovis-unexposed herds, historically negative, and a high-specificity diagnostic algorithm was developed. Serial test interpretation (positive on both) using the IGRA and IPRA showed significantly greater specificity (98.3%) than individual (90.4% and 80.9%, respectively) tests or parallel testing (73%). When the SCITT was added, the algorithm had 100% specificity. Since the cytokine assays had imperfect specificity, potential cross-reactivity with nontuberculous mycobacteria (NTM) was investigated. No association was found between NTM presence (in oronasal swab cultures) and positive cytokine assay results. As a proof-of-principle, serial testing was applied to buffaloes (n = 153) in a historically bTB-free herd. Buffaloes positive on a single test (n = 28) were regarded as test-negative. Four buffaloes were positive on IGRA and IPRA, and M. bovis infection was confirmed by culture. These results demonstrate the value of using IGRA and IPRA in series to screen buffalo herds with no previous history of M. bovis infection.