If the topological insulator Bi2Se3 is doped with electrons, superconductivity with Tc = 3–4 K emerges for a low density of carriers (n = 1020 cm−3) and with a small ratio of the superconducting coherence length and Fermi wave length: ξ/λ F = 2…4. These values make fluctuations of the superconducting order parameter increasingly important, to the extend that the Tc-value is surprisingly large. Strong spin–orbit interaction led to the proposal of an odd-parity pairing state. This begs the question of the nature of the transition in an unconventional superconductor with strong pairing fluctuations. We show that for a multi-component order parameter, these fluctuations give rise to a nematic phase at Tnem > Tc. Below Tc several experiments demonstrated a rotational symmetry breaking where the Cooper pair wave function is locked to the lattice. Our theory shows that this rotational symmetry breaking, as vestige of the superconducting state, already occurs above Tc. The nematic phase is characterized by vanishing off-diagonal long range order, yet with anisotropic superconducting fluctuations. It can be identified through direction-d ... mehrependent para-conductivity, lattice softening, and an enhanced Raman response in the Eg symmetry channel. In addition, nematic order partially avoids the usual fluctuation suppression of Tc.