We report observational analyses and theoretical interpretations of unusually red galaxies in the Subaru Deep Field (SDF). A careful analysis of the SDF data revealed a population with unusually red near-infrared (NIR) colors of J - K >~ 3-4, with higher confidence than the previous SDF result. Their surface number density drastically increases at K >~ 22 and becomes roughly the same with that of dusty starburst galaxies detected by submillimeter observations in recent years. These colors are even redder than the known population of the extremely red objects (EROs), and too red to explain by passively evolving elliptical galaxies which are the largest population of EROs. Hence these hyper extremely red objects (HEROs) should be considered as a distinct population from EROs. We discuss several possible interpretations of these enigmatic objects, and we show that these red NIR colors, K-band and sub-mm flux, and surface number density are quantitatively best explained by primordial elliptical galaxies reddened by dust, still in the starburst phase of their formation at z ~ 3.