A state of matter with a multi-component order parameter can give rise to vestigial order. In the vestigial phase, the primary order is only partially melted, leaving a remaining symmetry breaking behind, an effect driven by strong classical or quantum fluctuations. Vestigial states due to primary spin and charge-density-wave order have been discussed in iron-based and cuprate materials. Here we present the observation of a partially melted superconductivity in which pairing fluctuations condense at a separate phase transition and form a nematic state with broken Z₃, i.e., three-state Potts-model symmetry. Thermal expansion, specific heat and magnetization measurements of the doped topological insulators Nb_xBi₂Se₃ and Cu_xBi₂Se₃ reveal that this symmetry breaking occurs at T_nem ≃ 3.8 K above T_c ≃ 3.25 K, along with an onset of superconducting fluctuations. Thus, before Cooper pairs establish long-range coherence at T_c, they fluctuate in a way that breaks the rotational invariance at T_nem and induces a crystalline distortion.