We give an upper bound for the trace of a Hecke operator acting on the space of holomorphic cusp forms with respect to certain congruence subgroups. Such an estimate has applications to the analytic theory of elliptic curves over a finite field, going beyond the Riemann hypothesis over finite fields. As the main tool to prove our bound on traces of Hecke operators, we develop a Petersson formula for newforms for general nebentype characters.