O Colégio Militar teve a sua remota origem no "Colégio de Educação do Regimento de Artilharia da Corte" fundado em 1802/1803 pelo então Coronel António Teixeira Rebelo, comandante do Regimento de Artilharia da Corte sito no Forte da Feitoria, em Oeiras, com o objectivo de educar os filhos dos oficiais daquele regimento. Preocupado com a ocupação e educação das crianças e jovens familiares da sua guarnição e de civis da região, cria, desse modo, uma escola cujos agentes de ensino seriam os próprios militares do seu Regimento. Os alunos eram inicialmente cerca de vinte.
Em 1805, o Príncipe Regente, futuro D. João VI, manda conceder uma pensão aos educandos daquela escola; e, no ano seguinte, ele próprio visita as instalações da Feitoria, atraído pela fama do pequeno colégio, e ordena que seja aumentada aquela pensão e concedida uma gratificação mensal aos professores. Sempre interessado pelo colégio, o mesmo soberano confere, em 1807, um louvor a Teixeira Rebelo e aos seus colaboradores.
1807 é igualmente o ano em que Teixeira Rebelo deixa o comando do Regimento de Artilharia da Corte, sendo nomeado inspector dos Corpos de Artilharia. O Governo, certamente interessado no prosseguimento da acção educativa de Teixeira Rebelo, autorizou-o a manter-se nas suas funções directivas do Colégio, dando-se os primeiros passos para a autonomização da escola.
Em 1813, o colégio passa a ter existência oficialmente autónoma, adoptando a designação de Real Colégio Militar, com Teixeira Rebelo como director, entretanto promovido a Marechal de Campo.
O Real Colégio Militar foi transferido em 1814 do Forte da Feitoria para o edifício onde desde 1618 funcionara o Hospital de Nossa Senhora dos Prazeres, no sítio da Luz, em Lisboa, aí permanecendo até 1835.
Entre 1835 e 1859, o colégio mudou duas vezes de local (primeiro, para o sítio de Rilhafoles, no centro de Lisboa, e depois para o Convento de Mafra). Em 1859 voltou para a Luz, onde ainda hoje se mantém. Desde essa época que os alunos do Colégio Militar recebem o epíteto de "Meninos da Luz".
Com a implantação da República em 1910, o colégio perdeu o título de "Real", passando a denominar-se Colégio Militar.