Cytoskeletal (CSK) dynamics such as remodeling and reorganization can be studied by tracking the spontaneous motion of CSK-bound particles. Particle motion is thought to be driven by local, ATP-dependent intracellular force fluctuations due to polymerization processes and motor proteins, and to be impeded by a viscoelastic, metastable cytoskeletal network. The mechanisms that link particle motion to force fluctuations and the CSK dynamics remain unclear. We report simultaneous measurements of the spontaneous motion of CSK-bound particles and of cellular force fluctuations. Cellular force fluctuations were measured by tracking fluorescent markers embedded in an elastic polyacrylamide hydrogel substrate that served as an extracellular matrix (ECM). The motion of CSK-bound particles and markers embedded in the ECM showed both persistence and superdiffusive behavior. Moreover, the movements of CSK-bound beads were temporally and spatially correlated with force fluctuations in the ECM. The findings suggest that the spontaneous motion of CSK-bound beads is driven not by random, local stress fluctuations within a viscoelastic continuum or cage, but rather by stress fluctuations within a tensed and constantly remodeling CSK network that transmits stresses over considerable distances to the ECM.