Using the Atacama Large Millimeter/submillimeter Array, we have conducted a blind redshift survey in the 3 mm atmospheric transmission window for 26 strongly lensed dusty star-forming galaxies (DSFGs) selected with the South Pole Telescope. The sources were selected to have S 1.4 mm > 20 mJy and a dust-like spectrum and, to remove low-z sources, not have bright radio (S 843 MHz100 μm60 μm12CO, 13CO, C I, H2O, and H2O. We find one or more spectral features in 23 sources yielding a ~90% detection rate for this survey; in 12 of these sources we detect multiple lines, while in 11 sources we detect only a single line. For the sources with only one detected line, we break the redshift degeneracy with additional spectroscopic observations if available, or infer the most likely line identification based on photometric data. This yields secure redshifts for ~70% of the sample. The three sources with no lines detected are tentatively placed in the redshift desert between 1.7 . We find one or more spectral features in 23 sources yielding a ~90% detection rate for this survey; in 12 of these sources we detect multiple lines, while in 11 sources we detect only a single line. For the sources with only one detected line, we break the redshift degeneracy with additional spectroscopic observations if available, or infer the most likely line identification based on photometric data. This yields secure redshifts for ~70% of the sample. The three sources with no lines detected are tentatively placed in the redshift desert between 1.7 3. We discuss the effect of gravitational lensing on the redshift distribution and compare our measured redshift distribution to that of models in the literature.