L'église Saint-Martin a été construite dans la citadelle de Montmédy Haut, place forte dont une partie des remparts est due à Vauban, entre 1753 et 1757. Elle fut édifiée pour les besoins de la population et de la garnison. Son plan simple est typique des églises de villes de garnison du XVIIe et XVIIIe siècles. L'église se compose de trois nefs voûtées d'arêtes et d'un chevet polygonal. Une chapelle hors œuvre, la « chapelle Malandry », a été greffée au niveau du bas-côté nord dès la construction de l'édifice.
L'église est classée au titre des monuments historiques par arrêté du 19 janvier 1932, et le buffet d'orgue par arrêté du 17 décembre 1993. L'église a fait l'objet de plusieurs campagnes de restauration dont le clos-couvert (2000-2005) et les intérieurs (2007-2013). La restauration du clos-couvert de la nef, du chœur et des bas-côtés visait à renouveler entièrement la couverture en ardoise et à restaurer la charpente en conservant au maximum les bois d'origine.
Les travaux des intérieurs s'inscrivent dans le prolongement des travaux réalisés dans les années 1990 suite à des désordres importants liés à des chutes de moellons. Ils ont consisté à reprendre la maçonnerie, les enduits et les badigeons des murs de la nef, des bas-côtés et des voûtes. Les lambris et les stalles en bois présents dans le chœur, eux aussi protégés au titre des monuments historiques (arrêté du 20 juin 1933), ont également été restaurés. Une nouvelle campagne de travaux d'aménagement intérieur (mise en place de l’électricité et du chauffage) va commencer prochainement à la suite de la désacralisation de l'église Saint-Martin. Celle-ci conservera une fonction cultuelle mais ne recevra plus les offices dominicaux. Elle est destinée à devenir un centre culturel présentant des expositions et des concerts.
La partie instrumentale de l'orgue ayant été démontée par les troupes allemandes lors de l'occupation de la citadelle en 1917, l'opération de restauration du buffet d'orgue du XVIIIe siècle et la création d'un instrument neuf ont donc été menée en parallèle entre 2009 et 2013. L'opération a été supervisée par Mr Christian Lutz, technicien conseil pour les orgues. La restauration du buffet et la création de la partie phonique ont eu lieu dans l'atelier de l'entreprise Muhleisen à Eschau. Le buffet d'orgue a été démonté puis transporté pour restauration dans ces locaux.
La principale contrainte de cette opération était de respecter au maximum le buffet classé au titre des Monuments Historiques lors de l'implantation de l'orgue neuf. La restauration de la peinture faux-bois existante sur la façade et les parois latérales a été réalisée par l'entreprise Eschlimann avant la restauration de la menuiserie par le facteur d'orgue. Les graffiti présents sur les panneaux et témoins de l'histoire de la citadelle ont été conservés. Les pièces neuves en chêne ont été recouvertes d'un enduit d'une teinte différente de celle des pièces anciennes, différence visible de près mais invisible depuis la nef, respectant ainsi les principes déontologiques de la conservation-restauration. Le choix a été pris de ne pas restituer les parties manquantes de l'entablement du buffet dont aucune trace archéologique n'attestait la présence. La phase de remontage du buffet d'orgue et de l'instrument a eu lieu sur la tribune de la fin du mois de juin au mois de septembre 2013.
Financée à hauteur de 207 900 euros par le ministère de la Culture et de la Communication - DRAC Lorraine, le budget total des opérations sur l'église Saint-Martin s'élève à 630 000 euros.