The clustering of quasars on small scales yields fundamental constraints on models of quasar evolution and the buildup of supermassive black holes. This paper describes the first systematic survey to discover high redshift binary quasars. Using color-selection and photometric redshift techniques, we searched 8142 deg^2 of SDSS imaging data for binary quasar candidates, and confirmed them with follow-up spectroscopy. Our sample of 27 high redshift binaries (24 of them new discoveries) at redshifts 2.9 < z < 4.3 with proper transverse separations 10 kpc < R{perp} < 650 kpc increases the number of such objects known by an order of magnitude. Eight members of this sample are very close pairs with R{perp} < 100 kpc, and of these close systems four are at z > 3.5. The completeness and efficiency of our well-defined selection algorithm are quantified using simulated photometry and we find that our sample is ~ 50% complete. Our companion paper uses this knowledge to make the first measurement of the small scale clustering (R < 1 Mpc/h comoving) of high-redshift quasars. High redshift binaries constitute exponentially rare coincidences of two extreme (M >~ 10^9 Msun) supermassive black holes. At z ~ 4 there is about one close binary per 10 Gpc^3, thus these could be the highest sigma peaks, the analogs of superclusters, in the early Universe.