Protrusions at the leading-edge of a cell play an important role in sensing the extracellular cues during cellular spreading and motility. Recent studies provided indications that these protrusions wrap (coil) around the extracellular fibers. However, the physics of this coiling process, and the mechanisms that drive it, are not well understood. We present a combined theoretical and experimental study of the coiling of cellular protrusions on fibers of different geometry. Our theoretical model describes membrane protrusions that are produced by curved membrane proteins that recruit the protrusive forces of actin polymerization, and identifies the role of bending and adhesion energies in orienting the leading-edges of the protrusions along the azimuthal (coiling) direction. Our model predicts that the cell's leading-edge coils on fibers with circular cross-section (above some critical radius), but the coiling ceases for flattened fibers of highly elliptical cross-section. These predictions are verified by 3D visualization and quantitation of coiling on suspended fibers using Dual-View light-sheet microscopy (diSPIM). Overall, we provide a theoretical framework, supported by experiments, which explains the physical origin of the coiling phenomenon.