We present the results of a search for red QSOs using a selection based on optical imaging from SDSS and near-infrared imaging from UKIDSS. For a sample of 58 candidates 46 (79%) are confirmed to be QSOs. The QSOs are predominantly dust-reddened except a handul at redshifts z>3.5. The dust is most likely located in the QSO host galaxies. 4 (7%) of the candidates turned out to be late-type stars, and another 4 (7%) are compact galaxies. The remaining 4 objects we could not identify. In terms of their optical spectra the QSOs are similar to the QSOs selected in the FIRST-2MASS red Quasar survey except they are on average fainter, more distant and only two are detected in the FIRST survey. We estimate the amount of extinction using the SDSS QSO template reddened by SMC-like dust. It is possible to get a good match to the observed (restframe ultraviolet) spectra, but for nearly all the reddened QSOs it is not possible to match the near-IR photometry from UKIDSS. The likely reasons are that the SDSS QSO template is too red at optical wavelengths due to contaminating host galaxy light and that the assumed SMC extinction curve is too shallow. Our survey has demonstrated that selection of QSOs based on near-IR photometry is an efficent way to select QSOs, including reddened QSOs, with only small contamination from late-type stars and compact galaxies. This will be useful with ongoing and future wide-field near-IR surveys such as the VISTA and EUCLID surveys. [Abridged] ; Comment: 74 pages, 6 figures. Accepted for for publication in ApJS