We present initial results from the CO survey toward high redshift galaxies using the Nobeyama 45m telescope. Using the new wide bandwidth spectrometer equipped with a two-beam SIS receiver, we have robust new detections of three high redshift (z=1.6-3.4) submillimeter galaxies (SXDF 1100.001, SDP9, and SDP17), one tentative detection (SDSS J160705+533558), and one non-detection (COSMOS-AzTEC1). The galaxies observed during the commissioning phase are sources with known spectroscopic redshifts from previous optical or from wide-band submm spectroscopy. The derived molecular gas mass and line widths from Gaussian fits are ~10^11 Msun and 430-530 km/s, which are consistent with previous CO observations of distant submm galaxies and quasars. The spectrometer that allows a maximum of 32 GHz instantaneous bandwidth will provide new science capabilities at the Nobeyama 45m telescope, allowing us to determine redshifts of bright submm selected galaxies without any prior redshift information.