Em 1943, durante a Segunda Guerra Mundial, como conseqüência da decisão alemã de estender a campanha submarina ao Atlântico Sul, causando perdas ao nosso tráfego marítimo, foi criado este Centro, pelo Aviso nº 1881, de 23 de outubro de 1943, que recebeu, inicialmente, o nome de Centro de Instrução de Guerra Anti-Submarino (CIGAS) e, em seguida, de Centro de Instrução de Tática Anti-Submarino (CITAS). Sua missão era adestrar as guarnições dos navios da Marinha do Brasil, a fim de torná-las aptas ao combate contra submarinos inimigos.
Com o correr do tempo, à sua tarefa inicial de desenvolver táticas anti-submarino muitas outras se juntaram: tática aérea e de superfície, informações de combate, socorro e salvamento, controle de avarias, combate a incêndio, comunicações, aperfeiçoamento de oficiais e praças, etc. Em razão disso, recebeu o nome de Centro de Adestramento “Almirante Marques de Leão” (CAAML), em 22 de junho de 1951, em homenagem ao Almirante Joaquim Marques Baptista de Leão, um dos mais expressivos vultos navais da nossa história.
Nos anos 60, o Centro recebeu seu primeiro simulador que foi amplamente utilizado no adestramento das tripulações de navios de superfície, na antiga sede, localizada na Ilha das Cobras, em um prédio do Arsenal de Marinha do Rio de Janeiro.  Nos anos 70, o Centro entrou na era da informática, com a criação do Grupo de Sistemas. Preparava-se, assim, para adestrar as tripulações das novas e sofisticadas Fragatas Classe “Niterói”, que estavam para ser incorporadas.  Em 1985, o Centro mudou-se para as novas instalações na Ilha de Mocanguê, ficando, assim, mais próximo dos navios da Esquadra. Mantém, ainda, o Grupo de Socorro e Salvamento, localizado no Km 14 da Avenida Brasil. Trata-se do antigo Destacamento de Parada de Lucas - DPL - atualmente renomeado Grupo de Controle de Avarias (GruCav).
Suas  atividades   foram  regulamentadas, primeiramente,  no Decreto   n° 44.897,   de       27 de novembro de 1958, que aprovou o Regulamento para os Centros de Adestramento da Marinha  do  Brasil; posteriormente, pelo seu próprio  Regulamento  aprovado   por     meio da Portaria n° 1040, de  09 de  julho de 1976, do Ministro da Marinha. Revogada a Portaria de Regulamentação pela Portaria n° 0735, de 06 de agosto de 1987, do Ministro da Marinha,  passou  a  ter   as  suas  atividades  regidas,  sucessivamente,  por meio  da Portaria  n°  0029, de 21  de  agosto  de   1987,  do  Chefe  do  Estado-Maior  da  Armada (CEMA) e Portaria  n° 0058,  de  28  de junho   de 1996, do Comandante de Operações Navais (CON), alterada por meio da Portaria n° 022, de 06 de fevereiro de 1997. Revogadas as Portarias de regulamentação, passou a ter suas atividades regidas por um Regulamento,   aprovado  pela  Portaria  nº 0045 de 31 de  agosto de 1999, do CON.
O CAAML é subordinado ao Comando-em-Chefe da Esquadra e tem como atividade principal adestrar o pessoal que guarnece os navios da Esquadra, com ênfase no desempenho de Operações Navais e Controle de Avarias. Também realiza diversos cursos do Sistema de Ensino Naval, disseminando doutrinas táticas e procedimentos operativos, bem como instrução e adestramento para servidores militares e civis extra-Esquadra, de outras Forças Armadas, de Marinhas Amigas e de organizações civis governamentais e particulares. Atualmente, ministra mais de 40 diferentes cursos, com cerca de 7.000 alunos/ano. Além disso, realiza inspeções de verificação de desempenho das unidades de superfície da Esquadra.
O Centro de Adestramento “Almirante Marques de Leão”, conhecido como Camaleão, vem se modernizando continuamente, tanto pela aquisição e instalação de novos e sofisticados equipamentos e simuladores, como pelo preparo de pessoal, que tem a responsabilidade de ensinar
e adestrar os homens que guarnecem nossos navios.