We investigate the effects of roughness and fractality on the normal contact stiffness of rough surfaces. Samples of isotropically roughened aluminium surfaces are considered. The roughness and fractal dimension were altered through blasting using different sized particles. Subsequently, surface mechanical attrition treatment (SMAT) was applied to the surfaces in order to modify the surface at the microscale. The surface topology was characterised by interferometry based profilometry. The normal contact stiffness was measured through nanoindentation with a flat tip utilising the partial unloading method. We focus on establishing the relationships between surface stiffness and roughness, combined with the effects of fractal dimension. The experimental results, for a wide range of surfaces, showed that the measured contact stiffness depended very closely on surfaces root mean squared (RMS) slope and their fractal dimension, with correlation coefficients of around 90%, whilst a relatively weak correlation coefficient of 57% was found between the contact stiffness and RMS roughness.