Very little is known about the cosmological history from after the end of inflation until big bang nucleosynthesis. Various well-motivated models predict that the universe could have undergone a period of matter domination in this early epoch. We demonstrate that if the particles causing matter domination have self-interactions, they can form halos that undergo a gravothermal collapse. We thus propose a novel scenario for the formation of primordial black holes, which in particular can lie within the asteroid-mass range. We also find that it is not only black holes that can form in the aftermath of a gravothermal evolution. We show that number-changing annihilations of the particles can create sufficient heat to halt the gravothermal evolution, thus forming a "cannibal star." Likewise, the pressure from the particle's repulsive self-interactions can form a boson star during a gravothermal evolution. These stars can also eventually collapse into black holes. Thus, our study highlights that structure formation in the early universe can have a rich phenomenology.
