Natural stone was the primary building material in Cyprus in the past. Nowadays, its use is mostly confined to decorative purposes and restoration projects. This study represents the first thorough and systematic investigation of the characteristics of local carbonate stone. The variety of the results recorded highlights the complexity of this natural geomaterial and, hence, the particular attention needed before selecting the appropriate lithotype in construction practice. Stones coming from the same geological formation exhibit significant variations in their physico-mechanical properties. The materials’ durability against salt crystallization is explained with reference to their pore structure and flexural strength, revealing that, in many cases, small differences may have a significant impact on stone performance. The study also investigates the use of novel microdestructive techniques in the prediction of the mechanical properties of the stones under study. These techniques can be especially useful in the characterization of monumental stone, where sampling is limited, or when in situ characterization of stone is required.