We present the results of our first year of quasar search in the on-going ESO public Kilo Degree Survey (KiDS) and VISTA Kilo-Degree Infrared Galaxy (VIKING) surveys. These surveys are among the deeper wide-field surveys that can be used to uncovered large numbers of z~6 quasars. This allows us to probe a more common population of z~6 quasars that is fainter than the well-studied quasars from the main Sloan Digital Sky Survey. From this first set of combined survey catalogues covering ~250 deg^2 we selected point sources down to Z_AB=22 that had a very red i-Z (i-Z>2.2) colour. After follow-up imaging and spectroscopy, we discovered four new quasars in the redshift range 5.8<z<6.0. The absolute magnitudes at a rest-frame wavelength of 1450 A are between -26.6 < M_1450 < -24.4, confirming that we can find quasars fainter than M^*, which at z=6 has been estimated to be between M^*=-25.1 and M^*=-27.6. The discovery of 4 quasars in 250 deg^2 of survey data is consistent with predictions based on the z~6 quasar luminosity function. We discuss various ways to push the candidate selection to fainter magnitudes and we expect to find about 30 new quasars down to an absolute magnitude of M_1450=-24. Studying this homogeneously selected faint quasar population will be important to gain insight into the onset of the co-evolution of the black holes and their stellar hosts.