For the restoration of Saint Peter Dominican church (13th century A.D.) located in the city of Heraklion, Crete, the original building stones have been investigated in order to determine their mineralogical composition, their physical and mechanical properties, as well as the provenance area of the building stones. Drill cores and bulk samples of stones were taken from the monument for laboratory assessment. Two different types of rocks, a bioclastic limestone and a biocalcarenite, have determined as the main original construction materials. The lack of identical local stone, because of the cease of operation of the historic quarries in the area of Heraklion, from which the original stones was extracted, is the main problem concerning successful restoration. Locating an acceptable stone from working quarries located in the adjacent area of Rethymnon, using technical and aesthetic criteria, was the main objective of this investigation. Dimension stones from quarries were taken and tested in the laboratory. Physical properties like porosity, water absorption, compressive strength, mineralogical composition, colour variation and texture were used to select the appropriate new stone for the specific restoration and reconstruction works.