This paper presents the structural assessment and rehabilitation of two historical brick chimneys located at the site of the future North Gorge Eco-Sustainable Residential Development in Gibraltar. Originally built as part of the ventilation system for the Cold Stores complex—a heritage infrastructure dating back to the late nineteenth century—the chimneys had suffered significant degradation due to environmental exposure, vegetation growth, and lack of maintenance. A comprehensive survey campaign included 3D point cloud scans, visual inspections, material characterization, and ambient vibration tests to identify modal parameters and calibrate finite element models. The dynamic analysis revealed up to six distinct vibration modes, confirming the need for reinforcement. The retrofit strategy combined traditional conservation techniques, such as lime mortar repointing and brick substitution, with structural strengthening measures, including steel bands and crack stitching. While the South Chimney was preserved in situ, the North Chimney posed serious challenges in terms of accessibility and future maintenance, leading to an adaptive reuse approach. This study underscores the importance of integrating modern structural diagnostics with heritage preservation principles in the context of historical industrial assets.