Extensions of Einstein gravity with higher-order derivative terms are natural generalizations of Einsteins theory of gravity. They may arise in string theory and other effective theories, as well as being of interest in their own right. In this paper we study static black-hole solutions in the example of Einstein gravity with additional quadratic curvature terms in four dimensions. 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.