Cells navigating through complex tissues face a fundamental challenge: while multiple protrusions explore different paths, the cell needs to avoid entanglement. How a cell surveys and then corrects its own shape is poorly understood. Here, we demonstrate that spatially distinct microtubule dynamics regulate amoeboid cell migration by locally promoting the retraction of protrusions. In migrating dendritic cells, local microtubule depolymerization within protrusions remote from the microtubule organizing center triggers actomyosin contractility controlled by RhoA and its exchange factor Lfc. Depletion of Lfc leads to aberrant myosin localization, thereby causing two effects that rate-limit locomotion: (1) impaired cell edge coordination during path finding and (2) defective adhesion resolution. Compromised shape control is particularly hindering in geometrically complex microenvironments, where it leads to entanglement and ultimately fragmentation of the cell body. We thus demonstrate that microtubules can act as a proprioceptive device: they sense cell shape and control actomyosin retraction to sustain cellular coherence.