Over the last five years, the gauge/gravity correspondence has been applied to describe quantum critical systems at finite density. The simplest model to consider is Einstein-Maxwell gravity, and the ground state of the system is described by Reissner-Nordstrom black hole where all the charge is carried by the black hole. However, it turns out that this solution is unstable to the formation of both fermionic and bosonic matter, corresponding in the dual field theory to the creation of a Fermi surface and the onset of superconductivity, respectively. We consider Einstein-Maxwell system coupled to a perfect fluid of charged fermions and a charged scalar field. In addition to the black hole, electron star and holographic superconductor solutions, we find new asymptotically AdS 4 solutions, dual to 2+1 CFTs at zero temperature and finite chemical potential, which contain both scalar hair and an electron star. We compute the free energy and show that these new solutions are thermodynamically favoured when they exist. Moreover, we find evidence for a continuous phase transition between the holographic superconductor and the new solutions.