We determined the projected rotational velocity (v sin i) of 238 southern O stars selected from the Galactic O-star Survey. The sample contains 130 spectroscopic single stars (C), 36 single-lined binaries (SB1), and 72 SB2 systems (including eight triples). We applied the Fourier method to high-resolution spectra taken at Cerro Murphy, Chile, and supplemented by archival spectra. The overall v sin i statistics peaks at slow rotators (40-100 km/s) with a tail towards medium (100-200 km/s) and fast rotators (200-400 km/s). Binaries, on average, show increased rotation, which differs for close (P-orb < 10 d) and wide binaries (10 d < P-orb < 3700 d), and for primaries and secondaries. The spin-up of close binaries is well explained by the superposition of spin-orbit synchronisation and mass transfer via Roche-lobe overflow. The increased rotation of wide binaries, however, needs another explanation. Therefore, we discuss various spin-up mechanisms. Timescale arguments lead us to favour a scenario where wide O binaries are spun-up by a combination of cloud or disk fragmentation, which lays the basis of triple and multiple stars, and the subsequent merging or swallowing of low-mass by higher-mass stars or proto-stars.