Fresh concrete is composed of aggregates and cement paste, which itself is a dense suspension that exhibits a yield stress and serves as a binder that solidifies through cement hydration. Although there is relatively little reaction during the fresh state (i.e., before setting), there is still the formation of early hydration products that will influence the paste rheology. Nonzero stress at rest widely exists in concrete practice, e.g., interruption during pumping, static formwork casting, and 3D concrete printing, but its impact on eventual viscoelastic properties is not well understood. In this study, we investigated the influence of different levels of applied shear stress at rest on fresh cement pastes and show that it dramatically alters the eventual solid performance (i.e., static yield stress and stiffness). With increasing applied shear stress at rest, the cement paste exhibited increasing static yield stress and increasingly elastic behavior, where the origin was tied to the progression of hydration. Cement pastes were compared against magnesium oxide suspensions, which served as an inert model system, and an accelerated rate of static yield stress increase over time was observed in the former but not in the latter. This highlights the role of early cement hydration on the solidification behavior of fresh cement pastes in the presence of nonzero shear stress at rest. We further support this by showing that the structural evolution of cement paste under applied stress can primarily be attributed to an enhanced elastic limit, which is associated with early hydration. The influence of two common viscosity modifying admixtures, nanoclay and diutan gum, on these properties was also examined. This work demonstrates the importance of taking the shear stress at rest into consideration for laboratory rheological experiments and industrial concrete applications, as it can substantially impact the eventual solidification behavior.