Petrophysical and mechanical properties of sandstone reservoirs are likely to change as a result of faulting. In this paper, we investigate the distribution of deformation features (structures) such as fractures and deformation bands in the Navajo and the Entrada sandstones in the fault core and damage zones of two faults in two localities in southeast (Cache Valley) and central (San Rafael Swell) Utah. These two localities had different degree of calcite cementation and hence are of interest to study the mechanical and petrophysical properties of these localities, in order to find out the impact of cementation on these properties and their possible relations. We have performed in-situ measurements by Tiny-Perm II and Schmidt hammer to examine the distribution of permeability and strength/elasticity of rock within the damage zone of these faults. We have studied the statistical relation between (i) Tiny-Perm II measurements and Schmidt hammer values, (ii) permeability and uniaxial compressive strength, and (iii) permeability and Young's modulus of deformed rocks. The statistical results demonstrate that there are correlations between the studied parameters, but the dependencies vary with the degree of calcite cementation in mineralogically similar sandstones (quartz sandstone). Statistical results demonstrate to first approximation that an exponential law is more suitable for description of the relations (i), (ii) and (iii) of non-cemented Navajo sandstone whereas for cemented Navajo sandstone these relations are better approximated by power law