The state of preservation of built heritage monuments is often evaluated by means of several destructive techniques, which are mainly focused on the analysis of small parts of the monuments’ construction materials. The necessary sampling for the accomplishment of these destructive analyses is usually restricted to confined parts of a monument, since monuments are usually under protective legislation, and therefore only indicative of larger areas. Current research attempts to enhance the results of provided by destructive methods, using non-destructive image processing techniques. Towards this end, the potential use of image processing based on rectified images is examined, along with material sampling and laboratory analyses as part of a multi-disciplinary methodology for the investigation of Paphos (Cyprus) Harbour Castle. This approach has been adopted in order to map the degradation patterns observed on the monument’s masonry walls, minimizing destructive methods and attempting to visualize the results of the monument as a whole. The combination of both analytical and non-destructive techniques resulted in the acquisition of large amounts of information, permitting the evaluation of applied non-destructive techniques for the study of the deterioration present on a monument’s external surfaces. This approach led to the assessment of the overall state of preservation of the masonry walls of the structure in an extended scale covering all external façades in a semi-automatic way.