In a pilot search for high-redshift radio quasi-stellar objects (QSOs), we have obtained spectra of 55 FIRST sources (S1.4GHz > 1 mJy) with very red (O - E > 3) starlike optical identifications. 10 of the candidates are QSOs with redshifts 3.6 <z <4.4 (four were previously known), six with z > 4. The remaining 45 candidates comprise: one z = 2.6 broad-absorption-line (BAL) QSO; three low-redshift galaxies with narrow emission lines; 18 probable radio galaxies; and 23 M stars (mainly misidentifications). The success rate (high-redshift QSOs / spectroscopically-observed candidates) for this search is 1/2 for S1.4GHz > 10 mJy, and 1/9 for S1.4GHz > 1 mJy. With an effective search area of 4030deg2, the surface density of high-redshift (z > 4) QSOs discovered with this technique is 0.0015 deg-2.