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 the context of iron-based and cuprate materials. Here we present the observation of a partially melted superconductor in which pairing fluctuations condense at a separate phase transition and form a nematic state with broken Z3, i.e. three-state Potts-model symmetry. High-resolution thermal expansion, specific heat and magnetization measurements of the doped topological insulator NbxBi2Se3 reveal that this symmetry breaking occurs at Tnem=3.8 K above Tc=3.25 K, along with an onset of superconducting fluctuations. Thus, before Cooper pairs establish long-range coherence at Tc, they fluctuate in a way that breaks the rotational invariance at Tnem and induces a distortion of the crystalline lattice. Similar results are found for CuxBi2Se3.