We study the holographic complexity conjectures for rotating black holes, uncovering a relationship between the complexity of formation and the thermodynamic volume of the black hole. We suggest that it is the thermodynamic volume and not the entropy that controls the complexity of formation of large black holes in both the complexity equals action and complexity equals volume proposals in general. Our proposal reduces to known results involving the entropy in settings where the thermodynamic volume and entropy are not independent, but has broader scope. Assuming a conjectured inequality is obeyed by the thermodynamic volume, we establish that the complexity of formation is bounded from below by the entropy for large black holes.