The cosmological relaxion can address the hierarchy problem, while its coherent oscillations can constitute dark matter in the present universe. We consider the possibility that the relaxion forms gravitationally bound objects that we denote as relaxion stars. The density of these stars would be higher than that of the local dark matter density, resulting in enhanced signals in table-top detectors, among others. Furthermore, we raise the possibility that these objects may be trapped by an external gravitational potential, such as that of the Earth or the Sun. This leads to formation of relaxion halos of even greater density. We discuss several interesting implications of relaxion halos, as well as detection strategies to probe them.