The Falicov-Kimball model consists of spinless electrons and classical particles (ions) on a lattice. The electrons hop between nearest neighbor sites, while the ions do not. We consider the model with equal numbers of ions and electrons and with a large on-site attractive force between ions and electrons. For densities 1/4 and 1/5, the ion configuration in the ground state had been proved to be periodic. We prove that for density 2/9 it is periodic as well. However, for densities between 1/4 and 1/5 other than 2/9 we prove that the ion configuration in the ground state is not periodic. Instead there is phase separation. For densities in (1/5, 2/9) the ground-state ion configuration is a mixture of the density 1/5 and 2/9 ground-state ion configurations. For the interval (2/9, 1/4) it is a mixture of the density 2/9 and 1/4 ground states.