Development of new techniques to search for particles beyond the standard model is crucial for understanding the ultraviolet completion of particle physics. Several hypothetical particles are predicted to mediate exotic spin-dependent interactions between particles of the standard model that may be accessible to laboratory experiments. However, laboratory searches are mostly conducted for static spin-dependent interactions, with only a few experiments so far addressing spin- and velocity-dependent interactions. Here, we demonstrate a search for exotic spin- and velocity-dependent interactions with a spin-based amplifier. Our technique makes use of hyperpolarized nuclear spins as a pre-amplifier to enhance the effect of pseudo-magnetic field produced by exotic interactions by an amplification factor of > 100. Using such a spin-based amplifier, we establish constraints on the spin- and velocity-dependent interactions between polarized and unpolarized nucleons in the force range of 0.03-100 m. Our limits represent at least two orders of magnitude improvement compared to previous experiments. The established technique can be further extended to investigate other exotic spin-dependent interactions.