The stationary functional of the all-electron density functional plus dynamical mean field theory (DFT+DMFT) formalism to perform free energy calculations and structural relaxations is implemented for the first time. Here, the first order error in the density leads to a much smaller, second order error in the free energy. The method is applied to several well known correlated materials; metallic SrVO$_3$, Mott insulating FeO, and elemental Cerium, to show that it predicts the lattice constants with very high accuracy. In Cerium, we show that our method predicts the iso-structural transition between the $alpha$ and $gamma$ phases, and resolve the long standing controversy in the driving mechanism of this transition.