Os irmãos Lemes, fugidos de São Paulo em 1719, chegaram à região denominada hoje Cuiabá, via Camapuã – Coxim. A região começou a tornar-se mais conhecida quando, em 1722, por aqui passou Dom Rodrigo César de Menezes, na época governador da capitania de São Paulo que, aqui chegando, em 4 de março de 1727, assinou a concessão de três sesmarias nos sertões do Taquari, sendo a primeira a favor de João de Araújo Cabral; a segunda em 4 de abril, no Rio Taquari a favor do Sargento-Mor Manoel Lopes do Prado e, a terceira, ainda no Rio Taquari, em 31 de dezembro, a favor de Domingos Gomes Biliago.
Em 1729, Domingos Gomes Biliago uniu-se a Antônio de Sousa Bastos, Manoel Caetano e os Padres Antônio de Morais e José Frias e, à margem esquerda do Rio Taquari, fundaram o Arraial do Biliago, onde atualmente, na margem oposta (direita), se situa Coxim, cuja finalidade era o de socorrer as monções que iam de São Paulo até Cuiabá.
O arraial foi elevado à Freguesia em 1850, quando foi criado o Destacamento Militar do Piquiri, sendo Biliago incluído dentro dos seus limites.
Às margens de um rio navegável e com a estrada que ligava ao interior de Goiás, o arraial foi se desenvolvendo e em 1862, passou a ser chamado, Núcleo do Taquari com criação no lugar, de uma Colônia Militar, pelo Governador da Província, Herculano Ferreira Penna.
Em abril de 1865, o Núcleo é povoado por forças invasoras paraguaias, tendo seu comandante, Capitão Antônio Pedro, se retirado do povoado com 125 pessoas em direção ao norte do Estado. Em 8 de maio de 1866, a notícia da ocupação chegou à Cuiabá por Antônio Teodoro de Carvalho, morador na fazenda São Pedro, a oito léguas do Núcleo. Segundo um ofício do Capitão Antônio Pedro ao Presidente da Província, datado de 15 de maio de 1866, as forças invasoras que ocuparam o Núcleo compunham de 400 a 500 homens, com dois canhões que saquearam e incendiaram o povoado, abandonando-o depois de seis dias de ocupação.
Em 1872, o Núcleo foi elevado à categoria de Freguesia com a denominação de São José de Herculânia, em homenagem ao presidente Herculano Ferreira Penna. Em 1892, a Assembleia Legislativa apresentou ao presidente do Estado, uma Lei mudando o nome de Herculânia para Coxim que, acabou sendo vetada pelo Dr. Manoel José Murtinho.
O distrito foi criado em 6 de novembro de 1872 pela Lei n.° 1 e, finalmente, em 11 de abril de 1898, pela resolução n.° 202, a localidade é elevada a categoria de vila e município, substituiu-lhe finalmente Herculânia por Coxim, restituindo em 1944, pelo Interventor Júlio Müller. Em 1913, Coxim foi elevada à categoria de Comarca, sendo presidido pelo Juiz Amâncio Ramos, conservando-se o nome e os mesmos limites.
De 1916 a 1926, houve um período de turbulências, crimes e desgraças, com um maníaco subindo ao Poder, causando estrago na Comarca. Houve até a extinção da Comarca que, foi posteriormente restabelecida. Em 11 de outubro de 1977, o presidente Ernesto Geisel assinou a Lei Complementar n.º 31, que criou o Estado de Mato Grosso do Sul, e Coxim passa a fazer parte do novo Estado. Com a criação dos municípios de Camapuã, Rio Verde de Mato Grosso, Pedro Gomes e Alcinópolis, Coxim perdeu parte do seu grande território.