Recent theoretical studies with alkali atoms A* excited to high Rydberg states predicted the existence of ultra-long-range molecular bound states. Such excited dimers have large electric dipole moments which, in combination with their long radiative lifetimes, make them excellent candidates for manipulation in applications. This Letter reports on experimental investigations of the self-broadening of Rb principal series lines, which revealed multiple satellites in the line wings. The positions of the satellites agree quantitatively with theoretically predicted minima in the excited long-range Rydberg states of Rb2.