We conduct a search for radio stars by combining radio and optical data from the FIRST survey (Cat. VIII/71) and the Sloan Digital Sky Survey (SDSS-DR6, Cat. II/282, obsoleted by II/294). The faint limit of SDSS makes possible a homogeneous search for radio emission from stars of low optical luminosity. We select a sample of 112 candidate radio stars in the magnitude range 15<i<~19.1 and with radio flux S_20_>=1.25mJy, from about 7000deg^2^ of sky. The selection criteria are positional coincidence within 1", radio and optical point source morphology, and an SDSS spectrum classified as stellar. The sample contamination is estimated by random matching to be 108+/-13, suggesting that at most a small fraction of the selected candidates are genuine radio stars. Therefore, we rule out a very rare population of extremely radio-loud stars: no more than 1.2 of every million stars in the magnitude range 15<i<19.1 stars has radio flux S_20_>=1.25mJy. We investigate the optical and radio colors of the sample to find candidates that show the largest likelihood of being real radio stars. The significant outliers from the stellar locus, as well as the magnetically active stars, are the best candidates for follow-up radio observations.