Asymmetric stellar explosions impart an impulse, or natal kick, to their compact remnants by linear momentum conservation. Black hole (BH) natal kicks are often assumed to be weaker than neutron star kicks because of greater mass accretion, and they are harder to constrain observationally because isolated BHs are electromagnetically faint. Using 3D general-relativistic magnetohydrodynamic simulations lasting up to ~30 s, we show that BHs formed from the collapse of rapidly rotating massive stars (collapsars) threaded by strong large-scale magnetic fields can acquire large natal kicks 10^2–10^3 km/s. Asymmetric electromagnetic outflows, magnetic-flux eruptions, and the gravitational pull of aspherical ejecta shape the kick magnitude, and their relative contributions depend on the progenitor structure, magnetic-flux history, and BH spin. More rapidly spinning BHs receive stronger, more nearly spin-aligned kicks, primarily through the gravitational pull of asymmetric jet-driven ejecta. Delayed transitions to the magnetically arrested state produce more asymmetric outflows and can generate even stronger recoils. Because the large-scale magnetic flux required in our models is also a key ingredient of relativistic gamma-ray burst jets and their associated energetic, jet-driven supernovae, natal kicks may be a natural consequence of magnetized collapsars. Such kicks could substantially alter BH retention in dense stellar environments, binary survival, spin-orbit misalignment, and the viability of magnetized collapsars in producing highly spinning BHs within the pair-instability mass gap.