Methods, systems, and computer readable media for detecting a compromised computing host are disclosed. According to one method, the method includes receiving one or more domain name system (DNS) non-existent domain (NX) messages associated with a computing host. The method also includes determining, using a host score associated with one or more unique DNS zones or domain names included in the one or more DNS NX messages, whether the computing host is compromised. The method further includes performing, in response to determining that the computing host is compromised, a mitigation action.