We present a computational scheme for ab initio total-energy calculations of materials with strongly interacting electrons using a plane-wave basis set. It combines ab initio band structure and dynamical mean-field theory and is implemented in terms of plane-wave pseudopotentials. The present approach allows us to investigate complex materials with strongly interacting electrons and is able to treat atomic displacements, and hence structural transformations, caused by electronic correlations. Here it is employed to investigate two prototypical Jahn-Teller materials, KCuF3 and LaMnO3, in their paramagnetic phases. The computed equilibrium Jahn-Teller distortion and antiferro-orbital order agree well with experiment, and the structural optimization performed for paramagnetic KCuF3 yields the correct lattice constant, equilibrium Jahn-Teller distortion and tetragonal compression of the unit cell. Most importantly, the present approach is able to determine correlation-induced structural transformations, equilibrium atomic positions, and lattice structure in both strongly and weakly correlated solids in their paramagnetic phases as well as in phases with long-range magnetic order.