Human mesenchymal stem cells (hMSCs) are instrumental in the wound healing process. They migrate to wounds from their native niche in response to chemical signals released during the inflammatory phase of healing. At the wound, hMSCs downregulate inflammation and regulate tissue regeneration. Delivering additional hMSCs to wounds using cell-laden implantable hydrogels has the potential to improve healing outcomes and restart healing in chronic wounds. For these materials to be effective, cells must migrate from the scaffold into the native tissue. This requires cells to traverse a step-change in material properties at the implant-tissue interface. Migration of cells in material with highly varying properties is not well characterized. We measure 3D encapsulated hMSC migration and remodeling in a well-characterized hydrogel with a step-change in stiffness. This cell-degradable hydrogel is composed of 4-arm poly(ethylene glycol)-norbornene cross-linked with an enzymatically-degradable peptide. The scaffold is made with two halves of different stiffnesses separated by an interface where stiffness changes rapidly. We characterize changes in structure and rheology of the pericellular region using multiple particle tracking microrheology (MPT). MPT measures Brownian motion of embedded particles and relates it to material rheology. We measure more remodeling in the soft region of the hydrogel than the stiff region on day 1 post-encapsulation and similar remodeling everywhere on day 6. In the interface region, we measure hMSC-mediated remodeling along the interface and migration towards the stiff side of the scaffold. These results can improve materials designed for cell delivery from implants to a wound to enhance healing.