Extensions of Einstein gravity with higher-order derivative terms arise in string theory and other effective theories, as well as being of interest in their own right. In this Letter we study static black-hole solutions in the example of Einstein gravity with additional quadratic curvature terms. A Lichnerowicz-type theorem simplifies the analysis by establishing that they must have vanishing Ricci scalar curvature. By numerical methods we then demonstrate the existence of further black-hole solutions over and above the Schwarzschild solution. We discuss some of their thermodynamic properties, and show that they obey the first law of thermodynamics.