The detection of gravitational waves from binary neutron stars is a major goal of the gravitational-wave observatories Advanced LIGO and Advanced Virgo. Previous searches for binary neutron stars with LIGO and Virgo neglected the component stars angular momentum (spin). We demonstrate that neglecting spin in matched-filter searches causes advanced detectors to lose more than 3% of the possible signal-to-noise ratio for 59% (6%) of sources, assuming that neutron star dimensionless spins, $cmathbf{J}/GM^2$, are uniformly distributed with magnitudes between 0 and 0.4 (0.05) and that the neutron stars have isotropically distributed spin orientations. We present a new method for constructing template banks for gravitational wave searches for systems with spin. We present a new metric in a parameter space in which the template placement metric is globally flat. This new method can create template banks of signals with non-zero spins that are (anti-)aligned with the orbital angular momentum. We show that this search loses more than 3% of the maximium signal-to-noise for only 9% (0.2%) of BNS sources with dimensionless spins between 0 and 0.4 (0.05) and isotropic spin orientations. Use of this template bank will prevent selection bias in gravitational-wave searches and allow a more accurate exploration of the distribution of spins in binary neutron stars.