We conducted an exploratory search for quasars at z~ 6 - 8, using the Early Data Release from United Kingdom Infrared Deep Sky survey (UKIDSS) cross-matched to panoramic optical imagery. High redshift quasar candidates are chosen using multi-color selection in i,z,Y,J,H and K bands. After removal of apparent instrumental artifacts, our candidate list consisted of 34 objects. We further refined this list with deeper imaging in the optical for ten of our candidates. Twenty-five candidates were followed up spectroscopically in the near-infrared and in the optical. We confirmed twenty-five of our spectra as very low-mass main-sequence stars or brown dwarfs, which were indeed expected as the main contaminants of this exploratory search. The lack of quasar detection is not surprising: the estimated probability of finding a single z>6 quasar down to the limit of UKIDSS in the 27.3 square degrees of the EDR is <5%. We find that the most important limiting factor in this work is the depth of the available optical data. Experience gained in this pilot project can help refine high-redshift quasar selection criteria for subsequent UKIDSS data releases.