We obtained spectra of 60 red, star-like objects (E <18.8) identified with FIRST radio sources, S1.4GHZ>1 mJy. Eight are quasi-stellar objects (QSOs) with redshiftz z > 3.6. Combined with our earlier pilot search, our sample of 121 candidates yields a total of 18 z > 3.6 QSOs (10 of these with z > 4.0). 8 per cent of candidates with 5 1.4GHz10 mJy are QSOs with z > 3.6. The surface density of E <18.8, S1.4GHZ >1 mJy, z <4 QSOs is 0.003 deg -2. This is currently the only well-defined sample of radio-loud QSOs at z > 4 selected independently of radio spectral index. The QSOs are highly luminous in the optical (eight have MB <-28, q 0 = 0.5, H0 = 50 km s-1 Mpc-1). The SEDs are as varied as those seen in optical searches for high-redshift QSOs, but the fraction of objects with weak (strongly self-absorbed) Lyα emission is marginally higher (3 out of 18) than for high-redshift QSOs from SDSS (5 out of 96).