Plasmodium sporozoites, the infective stage of the malaria parasite, move by gliding motility, a unique form of locomotion required for tissue migration and host cell invasion. TRAP, a transmembrane protein with extracellular adhesive domains and a cytoplasmic tail linked to the actomyosin motor, is central to this process. Forward movement is achieved when TRAP, bound to matrix or host cell receptors, is translocated posteriorly. It has been hypothesized that these adhesive interactions must ultimately be disengaged for continuous forward movement to occur. TRAP has a canonical rhomboid-cleavage site within its transmembrane domain and mutations were introduced into this sequence to elucidate the function of TRAP cleavage and determine the nature of the responsible protease. Rhomboid cleavage site mutants were defective in TRAP shedding and displayed slow, staccato motility and reduced infectivity. Moreover, they had a more dramatic reduction in infectivity after intradermal inoculation compared to intravenous inoculation, suggesting that robust gliding is critical for dermal exit. The intermediate phenotype of the rhomboid cleavage site mutants suggested residual, albeit inefficient cleavage by another protease. We therefore generated a mutant in which both the rhomboid-cleavage site and the alternate cleavage site were altered. This mutant was non-motile and non-infectious, demonstrating that TRAP removal from the sporozoite surface functions to break adhesive connections between the parasite and extracellular matrix or host cell receptors, which in turn is essential for motility and invasion.