ParA and ParB of Caulobacter crescentus belong to a conserved family of bacterial proteins implicated in chromosome segregation. ParB binds to DNA sequences adjacent to the origin of replication and localizes to opposite cell poles shortly following the initiation of DNA replication. ParA has homology to a conserved and widespread family of ATPases. Here, we show that ParB regulates the ParA ATPase activity by promoting nucleotide exchange in a fashion reminiscent of the exchange factors of eukaryotic G proteins. Furthermore, we demonstrate that ADP-bound ParA binds single-stranded DNA, whereas the ATP-bound form dissociates ParB from its DNA binding sites. Increasing the fraction of ParA-ADP in the cell inhibits cell division, suggesting that this simple nucleotide switch may regulate cytokinesis.