Anharmonic atomic motions can strongly influence the optoelectronic properties of materials but how these effects are connected to the underlying phonon band structure is not understood well. We investigate how the electronic band gap is influenced by overdamped phonons, which occur in an intriguing regime of phonon-phonon interactions where vibrational lifetimes fall below one oscillation period. We contrast the anharmonic halide perovskite CsPbBr_{3}, known to exhibit overdamped phonons in its cubic phase, with the anharmonic oxide perovskite SrTiO_{3} where the phonons are underdamped at sufficiently high temperatures. Our results show that overdamped phonons strongly impact the band gap and cause slow dynamic fluctuations of electronic levels that have been implicated in the unique optoelectronic properties of halide perovskites. This finding is enabled by developing augmented stochastic Monte Carlo methods accounting for phonon renormalization and imaginary modes that are typically neglected. Our work provides guidelines for capturing anharmonic effects in theoretical calculations of materials.