We determined the projected rotational velocity (vsini) 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 vsini statistics peaks at slow rotators (40-100km/s) with a tail towards medium (100-200km/s) and fast rotators (200-400km/s). Binaries, on average, show increased rotation, which differs for close (Porb<10d) and wide binaries (10d<Porb<3700d), 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.