O maior problema com que se deparou o governo de Prudente de Morais foi a sangrenta campanha de Canudos. Surgiu em 1893, no interior da Bahia, o cearense Antônio Vicente Mendes Maciel, posteriormente conhecido pelo apelido de Antônio Conselheiro. Apresentado-se como profeta, pregava entre os sertanejos analfabetos, esquecidos pelo império, a restauração da monarquia e a volta de D. Sebastião, Rei de Portugal morto em 1578 na famosa batalha de Alcácer-Quibir, o qual sairia das ondas do mar com todo o seu exército. Reuniu Antônio Conselheiro em torno de sua personalidade messiânica um grande número de seguidores que logo lhe atribuíram milagres extraordinários, estabelecendo-se às margens do Rio Vaza-Barris, em um vilarejo onde seria incontestável sua autoridade de santo. Chegou, no auge, a reunir no arraial entre 20 e 25 mil pessoas.

O governo da Bahia mandou uma pequena força policial a Canudos em 1896, pois a agitação promovida por Antônio Conselheiro punha em sobressalto os comerciantes e fazendeiros das vizinhanças. A expedição foi surpreendida por uma multidão de fanáticos que promoveu furioso contra-ataque, obrigando a retirada imediata dos soldados. Uma segunda expedição em dezembro do mesmo ano, com 600 homens foi de novo fragorosamente derrotada pelos jagunços.

Uma terceira expedição dessa vez com 1300 homens bem armados foi mandada para lá. Novo fracasso. Para piorar a situação governista, dessa vez os jagunços se apoderaram das bagagens e do armamento de uma brigada do exército.

A quarta expedição militar foi organizada pelo ministro da Guerra, Mal. Carlos Machado Bittencourt, que partiu para a base de operações na Bahia. Composta de 6 brigadas, perfazendo quase 6000 homens. Contava com artilharia de grosso calibre. A fome, a sede, o calor e a resistência fanática dos jagunços tornaram a expedição uma das mais dramáticas páginas da história republicana. A 30 de setembro de 1897 foi desfechado o ataque final. Os jagunços famintos, sedentos e esfarrapados defenderam palmo a palmo seus últimos redutos. A 5 de outubro, pouco restava do arraial sertanejo. Um incêndio, ateado com querosene e dinamite destruiu os numerosos casebres que compunham a estranha cidadela do sertão nordestino. Antônio Conselheiro estava morto e com ele milhares de jagunços. O exército havia perdido também cerca de 4000 homens para destruir Canudos.

Antônio Conselheiro fora considerado um inimigo da República, quando na verdade viveu apenas um drama messiânico e dirigiu com sua personalidade psicopática o fanatismo religioso de uma pobre população, cujo atraso, evidentemente, jamais permitiria a compreensão das diferenças entre República e Monarquia. A Campanha de Canudos poderia ter sido evitada com escolas, saúde pública, ajuda econômica e assistência social. Preferiu-se a pior solução: o extermínio pelo fogo de um pungente drama social.