Enzymes that cut proteins inside membranes regulate diverse cellular events, including cell signaling, homeostasis, and host-pathogen interactions. Adaptations that enable catalysis in this exceptional environment are poorly understood. We visualized single molecules of multiple rhomboid intramembrane proteases and unrelated proteins in living cells (human and Drosophila) and planar lipid bilayers. Notably, only rhomboid proteins were able to diffuse above the Saffman-Delbruck viscosity limit of the membrane. Hydrophobic mismatch with the irregularly shaped rhomboid fold distorted surrounding lipids and propelled rhomboid diffusion. The rate of substrate processing in living cells scaled with rhomboid diffusivity. Thus, intramembrane proteolysis is naturally diffusion-limited, but cells mitigate this constraint by using the rhomboid fold to overcome the "speed limit" of membrane diffusion.