We propose a novel experimental approach to explore exotic spin-dependent interactions using a spin-exchange relaxation-free (SERF) magnetometer, the most sensitive non-cryogenic magnetic-field sensor. This approach studies the interactions between optically polarized electron spins located inside a vapor cell of the SERF magnetometer and unpolarized or polarized particles of external solid-state objects. The coupling of spin-dependent interactions to the polarized electron spins of the magnetometer induces the tilt of the electron spins, which can be detected with high sensitivity by a probe laser beam similarly as an external magnetic field. We estimate that by moving unpolarized or polarized objects next to the SERF Rb vapor cell, the experimental limit to the spin-dependent interactions can be significantly improved over existing experiments, and new limits on the coupling strengths can be set in the interaction range below 0.01 m.