La província de Batna (en àrab:ولاية باتنة) és una província (wilaya) d'Algèria. La capital és la ciutat de Batna, té una població de 962.623 habitants i una àrea de 12.038 km2.
Coord.: 35° 46′ 32″ N, 006° 03′ 12″ E / 35.77556,6.05333