We consider the nonlinear heat equation $u_t - Delta u = |u|^alpha u$ on ${mathbb R}^N$, where $alpha >0$ and $Nge 1$. We prove that in the range $0 < alpha <frac {4} {N-2}$, for every $mu >0$, there exist infinitely many sign-changing, self-similar solutions to the Cauchy problem with initial value $u_0 (x)= mu |x|^{-frac {2} {alpha }}$. The construction is based on the analysis of the related inverted profile equation. In particular, we construct (sign-changing) self-similar solutions for positive initial values for which it is known that there does not exist any local, nonnegative solution.