Sequence-specific DNA-binding proteins must quickly and reliably localize specific target sites on DNA. This search process has been well characterized for monomeric proteins, but it remains poorly understood for systems that require assembly into dimers or oligomers at the target site. We present a single-molecule study of the target-search mechanism of protelomerase TelK, a recombinase-like protein that is only active as a dimer. We show that TelK undergoes 1D diffusion on non-target DNA as a monomer, and it immobilizes upon dimerization even in the absence of a DNA target site. We further show that dimeric TelK condenses non-target DNA, forming a tightly bound nucleoprotein complex. Together with theoretical calculations and molecular dynamics simulations, we present a novel target-search model for TelK, which may be generalizable to other dimer and oligomer-active proteins.