A origem do AGCRJ remonta à época da refundação da cidade, por Mem de Sá, no morro do Castelo em 1567, quando foi constituído o Arquivo da Câmara Municipal. Esse Arquivo tinha como finalidade guardar a documentação gerada e acumulada pela Câmara, que, obedecendo à legislação portuguesa, desempenhava tanto funções legislativas quanto executivas na administração da "muito leal e heróica cidade do Rio de Janeiro".
No século XVIII, com o crescimento da cidade, a Câmara Municipal passou a deliberar sobre uma gama mais vasta de assuntos, passando a produzir um número maior de documentos versando sobre temas diversificados. Em 1790, um incêndio criminoso nessa Casa destruiu grande parte do acervo arquivístico. Entretanto, os vereadores determinaram que fossem feitas cópias dos documentos relativos à municipalidade, existentes em outros órgãos administrativos, conseguindo reconstituir uma parte da documentação perdida, especialmente os registros de terras, que foram o alvo principal do incêndio, já que continham informações sobre a propriedade de terrenos e de imóveis, em várias regiões da cidade.