The RecA family of ATPases mediates homologous recombination, a reaction essential for maintaining genomic integrity and for generating genetic diversity. RecA, ATP and single-stranded DNA (ssDNA) form a helical filament that binds to double-stranded DNA (dsDNA), searches for homology, and then catalyses the exchange of the complementary strand, producing a new heteroduplex. Here we have solved the crystal structures of the Escherichia coli RecA-ssDNA and RecA-heteroduplex filaments. They show that ssDNA and ATP bind to RecA-RecA interfaces cooperatively, explaining the ATP dependency of DNA binding. The ATP gamma-phosphate is sensed across the RecA-RecA interface by two lysine residues that also stimulate ATP hydrolysis, providing a mechanism for DNA release. The DNA is underwound and stretched globally, but locally it adopts a B-DNA-like conformation that restricts the homology search to Watson-Crick-type base pairing. The complementary strand interacts primarily through base pairing, making heteroduplex formation strictly dependent on complementarity. The underwound, stretched filament conformation probably evolved to destabilize the donor duplex, freeing the complementary strand for homology sampling.