The lateral mobility of proteins within cell membranes is usually thought to be dependent on their size and modulated by local heterogeneities of the membrane. Experiments using single-particle tracking on reconstituted membranes demonstrate that protein diffusion is significantly influenced by the interplay of membrane curvature, membrane tension, and protein shape. We find that the curvature-coupled voltage-gated potassium channel (KvAP) undergoes a significant increase in protein mobility under tension, whereas the mobility of the curvature-neutral water channel aquaporin 0 (AQP0) is insensitive to it. Such observations are well explained in terms of an effective friction coefficient of the protein induced by the local membrane deformation.