Mdm2 is a nucleoplasmic and nucleolar protein interacting with p53 and alternative reading frame (ARF) tumor suppressor proteins. Here we demonstrate relocalization and novel interactions of Mdm2 with the promyelocytic leukemia (PML) protein following cellular stress and DNA damage. We show that Mdm2 and PML interact directly in vivo and in vitro depending on the Mdm2 RING finger domain and the PML C-terminus, and that Mdm2 is recruited to the PML nuclear bodies by overexpression of PML. Cellular stress and DNA damage caused by UV-radiation, downregulation of the proteasome and arsenic trioxide promoted Mdm2 and PML damage-specific nuclear relocalization and interaction in a p53-independent manner. However, in vitro analyses showed that PML, Mdm2 and p53 form trimeric complexes. UV-radiation caused rapid rearrangements of PML nuclear bodies and promoted PML-p53 and PML-Mdm2 complex formation, coinciding with p53 stabilization and preceding p53-Mdm2 interaction suggesting temporally distinct complexes. The results demonstrate novel associations between Mdm2 and PML and show the capacity of PML to participate in the activation and stabilization of p53 in response to cellular stress through PML interaction with Mdm2.