We show that the problem of stabilization of extra dimensions in Kaluza-Klein type cosmology may be solved in a theory of gravity involving high-order curvature invariants. The method suggested (employing a slow-change approximation) can work with a rather general form of the gravitational action. As examples, we consider pure gravity with Lagrangians quadratic and cubic in the scalar curvature and some more complex ones in a simple Kaluza-Klein framework. After a transition to the 4D Einstein conformal frame, this results in effective scalar field theories with certain effective potentials, which in many cases possess positive minima providing stable small-size extra dimensions. Estimates made in the original (Jordan) conformal frame show that the problem of a small value of the cosmological constant in the present Universe is softened in this framework but is not solved completely. © 2006 The American Physical Society.