The ubiquitin-related modifier SUMO regulates a wide range of cellular processes by post-translational modification with one, or a chain of SUMO molecules. Sumoylation is achieved by the sequential action of several enzymes in which the E2, Ubc9, transfers SUMO from the E1 to the target mostly with the help of an E3 enzyme. In this process, Ubc9 not only forms a thioester bond with SUMO, but also interacts with SUMO noncovalently. Here, we show that this noncovalent interaction promotes the formation of short SUMO chains on targets such as Sp100 and HDAC4. We present a crystal structure of the noncovalent Ubc9-SUMO1 complex, showing that SUMO is located far from the E2 active site and resembles the noncovalent interaction site for ubiquitin on UbcH5c and Mms2. Structural comparison suggests a model for poly-sumoylation involving a mechanism analogous to Mms2-Ubc13-mediated ubiquitin chain formation.