Medical device-associated staphylococcal infections are a common and challenging problem. However, detailed knowledge of staphylococcal biofilm dynamics on clinically relevant surfaces is still limited. In the present study, biofilm formation of the Staphylococcus aureus ATCC 25923 strain was studied on clinically relevant materials—borosilicate glass, plexiglass, hydroxyapatite, titanium and polystyrene—at 18, 42 and 66 h. Materials with the highest surface roughness and porosity (hydroxyapatite and plexiglass) did not promote biofilm formation as efficiently as some other selected materials. Matrix-associated poly-N-acetyl-β-(1-6)-glucosamine (PNAG) was considered important in young (18 h) biofilms, whereas proteins appeared to play a more important role at later stages of biofilm development. A total of 460 proteins were identified from biofilm matrices formed on the indicated materials and time points—from which, 66 proteins were proposed to form the core surfaceome. At 18 h, the appearance of several r-proteins and glycolytic adhesive moonlighters, possibly via an autolysin (AtlA)-mediated release, was demonstrated in all materials, whereas classical surface adhesins, resistance- and virulence-associated proteins displayed greater variation in their abundances depending on the used material. Hydroxyapatite-associated biofilms were more susceptible to antibiotics than biofilms formed on titanium, but no clear correlation between the tolerance and biofilm age was observed. Thus, other factors, possibly the adhesive moonlighters, could have contributed to the observed chemotolerant phenotype. In addition, a protein-dependent matrix network was observed to be already well-established at the 18 h time point. To the best of our knowledge, this is among the first studies shedding light into matrix-associated surfaceomes of S. aureus biofilms grown on different clinically relevant materials and at different time points.