The possible existence of deeply bound nuclear K-bar states will be discussed. The nuclear ground states of a K- in (pp), 3He, and 8Be are predicted to be discrete states with binding energies of 48, 108 and 113 MeV and widths of 61, 20 and 38 MeV, respectively. It is found that a substantial contraction of the surrounding nucleus is induced due to the strong attraction of the I=0 K-bar N pair, thus forming an unusually dense and cold nuclear medium. If such exotic states are confirmed experimentally, ``bound-kaon nuclear spectroscopy" would create a new paradigm in strangeness nuclear physics.