The spatiotemporal regulation of chromosome segregation and cell division in Caulobacter crescentus is mediated by two different P-loop ATPases, ParA and MipZ. Both of these proteins form dynamic concentration gradients that control the positioning of regulatory targets within the cell. Their proper localization depends on their nucleotide-dependent cycling between a monomeric and a dimeric state and on the ability of the dimeric species to associate with the nucleoid. In this study, we use a combination of genetic screening, biochemical analysis and hydrogen/deuterium exchange mass spectrometry to comprehensively map the residues mediating the interactions of MipZ and ParA with DNA. We show that MipZ has non-specific DNA-binding activity that relies on an array of positively charged and hydrophobic residues lining both sides of the dimer interface. Extending our analysis to ParA, we find that the MipZ and ParA DNA-binding sites differ markedly in composition, although their relative positions on the dimer surface and their mode of DNA binding are conserved. In line with previous experimental work, bioinformatic analysis suggests that the same principles may apply to other members of the P-loop ATPase family. P-loop ATPases thus share common mechanistic features, although their functions have diverged considerably during the course of evolution.