The redshift distribution of flat-spectrum radio sources with 5 GHz flux densities S5>~5 mJy is a key component in using current radio lens surveys to probe the cosmological model. We have constructed the first flat-spectrum radio sample in the flux density range 3-20 mJy. Our new sample has 33 sources; we have determined the redshifts of 14 of these (42% complete). The low mean redshift, ~=0.75, of our faintest sample needs to be confirmed by further observations to improve the sample completeness. We also increased the redshift completeness of several surveys of brighter flat-spectrum sources. While the mean redshift ~=1.1 of flat-spectrum samples fainter than 1 Jy is nearly constant, the fraction of the sources identifiable as quasars steadily drops from ~80% to ~10% as the flux density of the sources decreases.