DNA polymerase IV (pol IV) is expressed at increased levels in Escherichia coli cells suffering high levels of DNA damage. In a recent single-molecule imaging study, we demonstrated that elevating the pol IV concentration is not sufficient to provide access to binding sites on the nucleoid, suggesting that other factors may recruit pol IV to its substrates once the DNA becomes damaged. Here we extend this work, investigating the proteins UmuD and RecA as potential modulators of pol IV activity. UmuD promotes long-lived association of pol IV with the nucleoid, whereas its cleaved form, UmuD’, which accumulates in DNA-damaged cells, inhibits binding. In agreement with proposed roles for pol IV in homologous recombination, up to 40% of pol IV foci colocalise with a probe for RecA* nucleoprotein filaments in ciprofloxacin-treated cells. A hyperactive RecA mutant, recA (E38K), allows pol IV to bind the nucleoid even in the absence of exogenous DNA damage. In vitro, RecA(E38K) forms RecA*-like structures that can recruit pol IV, even on double-stranded DNA, consistent with a physical interaction between RecA and pol IV. Together, the results indicate that UmuD and RecA modulate the binding of pol IV to its DNA substrates, which frequently coincide with RecA* structures.