In spite of the nanoscale and single-molecule insights into nucleoid associated proteins (NAPs), their role in modulating the mesoscale viscoelasticity of entangled DNA has been overlooked so far. By combining microrheology and molecular dynamics simulation, we find that the abundant NAP "integration host factor" (IHF) lowers the viscosity of entangled λDNA 20-fold at physiological concentrations and stoichiometries. Our results suggest that IHF may play a previously unappreciated role in resolving DNA entanglements and in turn may be acting as a "genomic fluidizer" for bacterial genomes.