The cytoskeleton (CSK) of living cells is a crosslinked fiber network, subject to ongoing biochemical remodeling processes that can be visualized by tracking the spontaneous motion of CSK-bound microbeads. The bead motion is characterized by anomalous diffusion with a power-law time evolution of the mean square displacement (MSD), and can be described as a stochastic transport process with apparent diffusivity D and power-law exponent β: MSD ∼ D (t/t(0))(β). Here we studied whether D and β change with the time that has passed after the initial bead-cell contact, and whether they are sensitive to bead coating (fibronectin, integrin antibodies, poly-L-lysine, albumin) and bead size (0.5-4.5 µm). The measurements are interpreted in the framework of a simple model that describes the bead as an overdamped particle coupled to the fluctuating CSK network by an elastic spring. The viscous damping coefficient characterizes the degree of bead internalization into the cell, and the spring constant characterizes the strength of the binding of the bead to the CSK. The model predicts distinctive signatures of the MSD that change with time as the bead couples more tightly to the CSK and becomes internalized. Experimental data show that the transition from the unbound to the tightly bound state occurs in an all-or-nothing manner. The time point of this transition shows considerable variability between individual cells (2-30 min) and depends on the bead size and bead coating. On average, this transition occurs later for smaller beads and beads coated with ligands that trigger the formation of adhesion complexes (fibronectin, integrin antibodies). Once the bead is linked to the CSK, however, the ligand type and bead size have little effect on the MSD. On longer timescales of several hours after bead addition, smaller beads are internalized into the cell more readily, leading to characteristic changes in the MSD that are consistent with increased viscous damping by the cytoplasm and reduced binding strength.