Upon sustained loading, colloidal gels tend to feature delayed viscoplastic creep deformations. However, the relationship, if any, between the structure and creep dynamics of gels remains elusive. Here, based on accelerated molecular dynamics simulations and the recently developed softness approach (i.e., classification-based machine learning), we reveal that the propensity of a gel to exhibit long-time creep is encoded in its static, unloaded structure. By taking the example of a calcium–silicate–hydrate gel (the binding phase of concrete), we extract a local, non-intuitive structural descriptor (a revised version of the “softness” metric proposed by the pioneering work from Cubuk et al.) that is strongly correlated with the dynamics of the particles. Notably, the macroscopic creep rate exhibits an exponential dependence on the average softness. We find that creep results in a decrease in softness in the gel structure, which, in turn, explains the gradual decay of the creep rate over time. Finally, we demonstrate that the softness metric is strongly correlated with the average energy barrier that is accessible to the particles.