A computational scheme for the investigation of complex materials with strongly interacting electrons is formulated which is able to treat atomic displacements, and hence structural relaxation, caused by electronic correlations. It combines ab initio band structure and dynamical mean-field theory and is implemented in terms of plane-wave pseudopotentials. The equilibrium Jahn-Teller distortion and antiferro-orbital order found for paramagnetic KCuF3 agree well with experiment.