Distortions of the oxygen octahedra influence the fundamental electronic structure of perovskite oxides, such as their bandwidth and exchange interactions. Utilizing a fully ab-initio methodology based on density functional theory plus dynamical mean field theory (DFT+DMFT), we study the crystal and magnetic structure of SrMoO$_3$. Comparing our results with DFT+$U$ performed on the same footing, we find that DFT+$U$ overestimates the propensity for magnetic ordering, as well as the octahedral rotations, leading to a different ground state structure. This demonstrates that structural distortions can be highly sensitive to electronic correlation effects, and to the considered magnetic state, even in a moderately correlated metal such as SrMoO$_3$. Moreover, by comparing different downfolding schemes, we demonstrate the robustness of the DFT+DMFT method for obtaining structural properties, highlighting its versatility for applications to a broad range of materials.