Unconventional superconductivity is characterized by the spontaneous symmetry breaking of the macroscopic superconducting wavefunction in addition to the gauge symmetry breaking, such as rotational-symmetry breaking with respect to the underlying crystal-lattice symmetry. Particularly, superconductivity with spontaneous rotational-symmetry breaking in the wavefunction amplitude and thus in bulk properties, not yet reported previously, is intriguing and can be termed nematic superconductivity in analogy to nematic liquid-crystal phases. Here, based on specific-heat measurements of the single-crystalline Cu$_x$Bi$_2$Se$_3$ under accurate magnetic-field-direction control, we report thermodynamic evidence for nematic superconductivity, namely, clear two-fold-symmetric behavior in a trigonal lattice. The results indicate realization of an odd-parity nematic state, feasible only by macroscopic quantum condensates and distinct from nematic states in liquid crystals. The results also confirm topologically non-trivial superconductivity in Cu$_x$Bi$_2$Se$_3$.