Cohesin extrudes genomic DNA into loops that promote chromatin assembly, gene regulation, and gene recombination. Loop extrusion depends on large-scale conformational changes in cohesin, but how these translocate DNA is poorly understood. Here, we provide evidence that cohesin negatively supercoils DNA during loop extrusion. Supercoiling requires the engagement of cohesin’s ATPase heads, DNA clamping by these heads, and a DNA-binding site on cohesin’s hinge, indicating that cohesin twists DNA when constraining it between the hinge and the clamp. A cohesin mutant defective in negative supercoiling forms shorter loops in cells, and a similar, although weaker, phenotype is observed after the depletion of topoisomerase I. These results suggest that supercoiling is an integral part of the loop-extrusion mechanism and that relaxation of supercoiled DNA is required for cohesin-mediated loop extrusion and genome architecture.