Durable osseointegration of metallic bone implants requires that progenitor cells attach, proliferate and differentiate on the implant surface. Previously, we demonstrated superior biocompatibility of human mesenchymal stromal cells (MSCs) cultivated on ultrasmooth tantalum (Ta) as compared to titanium (Ti) surface. The aim of this study was to extend the previous investigation of biocompatibility by monitoring temporal gene expression of MSCs on topographically comparable smooth Ta and Ti surfaces using whole-genome gene expression analysis. Total RNA samples from telomerase-immortalized human MSCs cultivated on plain sputter-coated surfaces of Ta or Ti for 1, 2, 4, and 8 days were hybridized to n = 16 U133 Plus 2.0 arrays (Affymetrix^®). Functional annotation, cluster and pathway analyses were performed. The vast majority of genes were differentially regulated after 4 days of cultivation and genes upregulated by MSCs exposed to Ta and Ti were predominantly related to the processes of differentiation and transcription, respectively. Functional annotation analysis of the 1,000 temporally most significantly regulated genes suggests earlier cellular differentiation on Ta compared to Ti surface. Key genes related to osteogenesis and cell adhesion were upregulated by MSCs exposed to Ta. We further identified differentially regulated candidate transcription factors, e.g., NRF2, EGR1, IRF-1, IRF-8, NF-Y, and p53 as well as relevant signaling pathways, e.g., p53 and mTOR, indicating e.g., differences in the Ta- and Ti-induced oxidative stress reactions at the cell/biomaterial interface. These findings suggest that Ta is a promising material for bone implants.