O Clube Niteroiense de Montanhismo - CNM - surgiu da iniciativa de alguns escaladores de Niterói integrantes da lista de emails da Federação de Esportes de Montanha do Estado do Rio de Janeiro - FEMERJ. Foi indagado na lista se existia algum clube excursionista em Niterói, e diante do fato da inexistência de um, houve a mobilização e assim no dia 26 de março de 2003 ocorreu a primeira reunião, reunindo muitos montanhistas niteroienses interessados na criação do clube.
Com o apoio da FEMERJ, demais clubes e escaladores independentes, o CNM começou a se organizar e tomar forma. Já a partir de 2003, o clube iniciou sua participação nas Aberturas da Temporada de Montanhismo, evento anual organizado pelos clubes filiados à federação. No início de 2004, começou o primeiro curso de formação de guias de montanha do clube, e instrutores de outros clubes se disponibilizaram a ajudar. Durante este tempo, diversas atividades ocorreram, caminhadas e escaladas em Niterói, no Rio e em outras localidades do estado.
No final de 2004, mais precisamente no dia 20 de novembro, foi realizada a Assembléia Geral de Fundação do CNM. Com esse importante passo, foi aprovado o estatuto e eleita a primeira Diretoria, representada por: Gustavo Muniz (presidente), Alan Marra (vice-presidente), Nise Caldas (tesoureira), Jerônimo dos Santos (diretoria técnica) e Alex Figueiredo (diretoria de meio-ambiente). Oficializado o clube, mais integrantes passaram a fazer parte, o que permitiu maior representatividade em Niterói.
Em 2005, o CNM assumiu a coordenação do Grupo de Trabalho (GT) Serra da Tiririca, iniciativa da FEMERJ. Com isso, alinhadas à administração do Parque Estadual da Serra da Tiririca, conduzida pelo Instituto Estadual de Florestas - IEF, várias atividades começaram a ser realizadas visando preservar o meio-ambiente local. Desde então, mutirões de limpeza, plantio de mudas e manutenção de trilhas tem ocorrido regularmente.
No dia 22 de novembro de 2005, um ano após a fundação, mais um momento importante para o CNM. Em Assembléia Geral Extraordinária da FEMERJ, o clube foi aceito pelas demais entidades que compõem a federação como o mais novo filiado. Desta forma, foi inserido efetivamente no contexto da organização do montanhismo estadual e nacional, uma vez que a federação integra a Confederação Brasileira de Montanhismo e Escalada - CBME.