We study the impurity entanglement entropy $S_e$ in quantum impurity models that feature a Kondo-destruction quantum critical point (QCP) arising from a pseudogap in the conduction-band density of states or from coupling to a bosonic bath. On the local-moment (Kondo-destroyed) side of the QCP, the entanglement entropy contains a critical component that can be related to the order parameter characterizing the quantum phase transition. In Kondo models describing a spin-$Simp$, $S_e$ assumes its maximal value of $ln(2Simp+1)$ at the QCP and throughout the Kondo phase, independent of features such as particle-hole symmetry and under- or over-screening. In Anderson models, $S_e$ is nonuniversal at the QCP, and at particle-hole symmetry, rises monotonically on passage from the local-moment phase to the Kondo phase; breaking this symmetry can lead to a cusp peak in $S_e$ due to a divergent charge susceptibility at the QCP. Implications of these results for quantum critical systems and quantum dots are discussed.