Damages due to fire occurred on many monuments and affected building sandstones. Changes in technical properties of heated sandstones are caused by changes in their structure and mineralogy. Therefore, a better knowledge of the changing processes in grain size scale is crucial to understand and assess property changes. The study presents results for the Cotta type Elbe Sandstone, a clay-bearing sandstone that is a widespread material for construction and sculpting. Uniaxial compressive strength and ultrasonic wave velocity as well as changes in colour, structures and mineralogical phases were determined for samples treated at temperatures of 300, 400, 500, 600, 700, 800 and 1250 °C and compared to the untreated material. The results show that minor clay components in the sandstone pores determine the uniaxial compressive strength in dependence of temperature and dry or wet state. Uniaxial compressive strength does not show a decrease even at high temperatures, whereas ultrasonic wave velocity is decreasing continuously with higher temperatures as for many other sandstones. The differing mechanical behaviour of the clay-bearing sandstone can be explained by the phase changes of kaolinite in the pore cement.