We present the first discovery of dust-reddened quasars (red quasars) in the high-z universe (z > 5.6). This is a result from the Subaru High-z Exploration of Low-Luminosity Quasars (SHELLQs) project, which is based on the sensitive multi-band optical imaging data produced by the Hyper Suprime-Cam (HSC) Subaru Strategic Program survey. We identified four red quasar candidates from the 93 spectroscopically confirmed high-z quasars in the SHELLQs sample, based on detections in the Wide-field Infrared Survey Explorer (WISE) data at 3.4 and 4.6 mu m (rest-frame similar to 5000-6500 angstrom). The amount of dust reddening was estimated with spectral energy distribution (SED) fits over optical and mid-infrared wavelengths. Two of the four candidates were found to be red quasars with dust reddening of E(B - V) > 0.1. The remaining SHELLQs quasars without individual WISE detections are significantly fainter in the WISE bands and bluer than the red quasars, although we did detect them in the W1 band in a stacked image. We also conducted the same SED fits for high-z optically-luminous quasars, but no red quasar was found. This demonstrates the power of Subaru HSC to discover high-z red quasars, which are fainter than the limiting magnitudes of past surveys in the rest-frame ultraviolet, due to dust extinction.