A la fin du Moyen Age, le corps de ville de Nancy siège en l'église Saint-Epvre ; les archives sont alors conservées dans la tour-porche de l'église. Au début du XVIIe siècle, l'hôtel de ville est établi sur la place du marché, dans la Ville-Neuve (actuelle place Charles III). Le conseil de ville ainsi que les archives s'y installent. En 1755, lors de la construction d'un nouvel hôtel de ville (sur l'actuelle place Stanislas), les archives de la ville trouvent place au-dessus des grands salons. Au début de la Seconde Guerre mondiale, en 1940, une grande partie des documents est déplacée à Bordeaux où elle se trouve encore en 1943. A la fin des années 1960, les archives sont transférées, dans le bâtiment actuel, ancienne manufacture de chaussures Spire et Coblentz datant du début du XXe siècle. Elles y cohabitent, quelque temps, avec la direction régionale de la Sécurité sociale, l'atelier de reliure municipal et l'atelier des décors du théâtre municipal.

Le bâtiment connaît deux restructurations successives, en 1982 et en 2001, permettant ainsi d'améliorer la capacité et les conditions d'accueil des documents et du public. Malgré ces opérations, le bâtiment ne correspond guère aux normes en vigueur.

C'est d'abord Henri Lepage, archiviste départemental, qui classe les archives de la ville à partir de 1864 et en fait l'inventaire. Dix ans plus tard, Emile Roussel, archiviste municipal nommé en 1875, poursuit le travail. Il publie, en 1891, la Table des délibérations du conseil municipal de 1789 à 1800. Son successeur, Paul Denis, prend ses fonctions en 1906 et quitte son poste en 1937. Après la Seconde Guerre mondiale, les Archives de Nancy restent sans titulaire. Rattachées au cabinet du maire, elles sont placées sous la surveillance lointaine d'un chef de bureau. En 1968, un poste de documentaliste-archiviste est créé en faveur de Michèle Renson. En mai 2005, Daniel Peter, jusqu'alors conservateur aux Archives départementales du Bas-Rhin, prend la direction de l'institution. Dès son arrivée, Daniel Peter réorganise toute l'institution. Une intense campagne d'éliminations est mise en place. Le service de la salle de lecture est désormais assuré par un roulement des agents. Il instaure un plan de classement des dossiers et du serveur. Ce plan sera également utilisé pour l'archivage des dossiers.