We study sums over primes of trace functions of l-adic sheaves. Using an extension of our earlier results on algebraic twists of modular forms to the case of Eisenstein series and bounds for Type II sums based on similar applications of the Riemann hypothesis over finite fields, we prove general estimates with power saving for such sums. We then derive various concrete applications.