The article presents the problem of selecting the correct type of limestone for producing paving stones used to renovate the surface of Mariacki Square in Krakow. Due to using up local limestone deposits, imported limestones began to be used. The first one was a Turkish limestone with the trade name Lotus Beige. Despite substantial physical and mechanical parameters (compressive strength 134 MPa, water absorption 0.26%), after several years of use, the paving stone cracked and, as a result, fell apart into smaller fragments. Hauteville limestone from France has been selected for the following reconstruction of the surface. This limestone in the air-dry state was characterised by even higher parameters, i.e. compressive strength of 157 MPa, flexural strength at 16.9 MPa, Bohme Abrasion test at 15275 mm3, and water absorption at 0.23%. The tests also showed absolute frost resistance and high resistance to thermal shock. Unfortunately, after several years of using the surface of Mariacki Square, cracks and flaking of the rock material have been observed in terms of some paving stones. These cracks appeared within the so-called stylolite seams, which are a natural feature of limestone. Despite a very strict selection of materials, unfortunately, problems with the surface’s durability could not be avoided.