Uma das principais atrações de Costa Marques é o Forte Príncipe da Beira que atualmente é mantido aberto pelo 1º Pelotão de Fuzileiros de Selva “destacamento do Exército Brasileiro”, sendo o único Forte brasileiro que não recebe recursos públicos para sua manutenção.
No século XVII havia na foz do Rio São Domingos, no Guaporé, uma povoação chamada Palmela, onde se instalara a Missão São José. Segundo registros de historiadores, o nome Palmela foi escolhido por um comerciante de Cuiabá, devido a uma tribo Caraíbas que habitava a região. Em 14 de março de 1769, D. Luís Pinto de Souza, governador da Capitania de Mato Grosso, determinou que fossem trocados os nomes de vários lugares, dentre eles o de São José, que passaria a se chamar Leomil, e o Sítio das Pedras, de Destacamento de Palmela.
