Let f be a holomorphic or Maass Hecke cusp form for the full modular group and write for the corresponding Hecke eigenvalues. We are interested in the signs of those eigenvalues. In the holomorphic case, we show that for some positive constant and every large enough x, the sequence has at least sign changes. Furthermore we show that half of non-zero are positive and half are negative. In the Maass case, it is not yet known that the coefficients are non-lacunary, but our method is robust enough to show that on the relative set of non-zero coefficients there is a positive proportion of sign changes. In both cases previous lower bounds for the number of sign changes were of the form x (delta) for some delta < 1.