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 standard-model particles that may be accessible to laboratory experiments. However, laboratory searches are mostly conducted for static spin-dependent interactions, with a few experiments addressing spin- and velocity-dependent interactions. Here, we demonstrate a search for these interactions with a spin-based amplifier. Our technique uses hyperpolarized nuclear spins as an amplifier for pseudo-magnetic fields produced by exotic interactions by a factor of more than 100. Using this technique, we establish constraints on the spin- and velocity-dependent interactions between polarized neutrons and unpolarized nucleons for the force range of 0.03 to 100 meters, improving previous constraints by at least two orders of magnitude in partial force range. This technique can be further extended to investigate other exotic spin-dependent interactions.