We confirm spectroscopically the existence of a population of galaxies at z>~2 with rest-frame optical colors similar to normal nearby galaxies. The galaxies were identified by their red near-infrared colors in deep images obtained with ISAAC on the Very Large Telescope. Redshifts of six galaxies with Js-Ks>2.3 were measured from optical spectra obtained with the Keck Telescope. Five out of six are in the range 2.43<=z<=3.52, demonstrating that the Js-Ks color selection is quite efficient. The rest-frame ultraviolet spectra of confirmed z>2 galaxies display a range of properties, with two galaxies showing emission lines characteristic of AGN, two having Ly-alpha in emission, and one showing interstellar absorption lines only. Their full spectral energy distributions are well described by constant star formation models with ages 1.4-2.6 Gyr, except for one galaxy whose colors indicate a dusty starburst. The confirmed z>2 galaxies are very luminous, with Ks=19.2-19.9. Assuming that our bright spectroscopic sample is representative for the general population of Js-Ks selected objects, we find that the surface density of red z>~2 galaxies is ~0.9/arcmin^2 to Ks=21. The surface density is comparable to that of Lyman-break selected galaxies with Ks<21, when corrections are made for the different redshift distributions of the two samples. Although there will be some overlap between the two populations, most optical-break galaxies are too faint in the rest-frame ultraviolet to be selected as Lyman-break galaxies. The most straightforward interpretation is that star formation in typical optical-break galaxies started earlier than in typical Lyman-break galaxies. Optical-break galaxies may be the oldest and most massive galaxies yet identified at z>2, and could evolve into early-type galaxies and bulges.