Ao início da Guerra do Paraguai, em dezembro de 1864, uma esquadra paraguaia, sob o comando do Capitão-de-Fragata Meza, invadiu a Província de Mato Grosso pelo Rio Paraguai, apossando-se de Forte de Coimbra e Albuquerque, e desembarcando em Corumbá. Ao ter notícia da invasão, o Presidente da Província, em Cuiabá, nomeou o Chefe de Esquadra Augusto Leverger para comandar a reação. Leverger conseguiu dissuadir o inimigo de subir os rios e atacar Cuiabá, e libertou Corumbá em 1867. A fim de fortificar definitivamente a Província de Mato Grosso, foi criada, em 20 de outubro de 1876, a Flotilha de Mato Grosso, três anos após a transferência dos estabelecimentos navais de Cuiabá para Ladário.

A Flotilha constituía-se, inicialmente, das seguintes unidades:

Encouraçado "Tamandaré",
Canhoneira Mista "Forte de Coimbra",
Canhoneiras de Rodas "Fernandes Vieira"
Canhoneiras de Rodas "Taquari";
Navios-Auxiliares: Monitores "Piaui", "Ceará", "Pará" e "Santa Catarina";
Vapores de Rodas "Corumbá" e "Antonio João".
A este grupo somavam-se, ainda, oito Lanchas a vapor, três Pontões, dois pequenos Vapores, sendo um a hélice, três Chatas, uma Chalana e uma Lancha a remos.