This study presents five different lithotypes of limestone containing stylolites and commonly used as dimension stones in Egypt, Hungary and Israel. All the studied limestones are generally hard, dense, with high degree of cementation and have high strength and low porosity. Stylolites are small tooth-like irregular surfaces most often developed on the carbonate-rich stones. Insoluble particles, i.e., organic matter, oxides and clays are usually incorporated within the stylolitic planes. The presence of stylolites and their filling materials generally has a large effect on the physical and mechanical properties of the host stones. The main aim of this study is to evaluate the damage mechanism of different stylolitic limestones and to understand the role of the clay in the deterioration of these stones. Hundred cube samples (2 cm) of all the studied limestones were subjected to 500 thermal cycles (10–70 °C) and 20 cube samples (3 cm) of a grey Israeli limestone with high open porosity were subjected to multiple wet/dry cycles. The changes in mass, strength, and ultrasound Vp velocity, were measured to follow any damage that happened due to cycling. The thermal cycling was proved to be an effective deterioration mechanism of both Egyptian and Hungarian lithotypes. The response of Israel grey lithotype to the wet/dry cycling was clearly shown by the splitting of the tested samples through the stylolite planes and the sharp decrease of their strength.