Systems and methods are described for scanning or monitoring of Domain Name System (DNS) records of an entity for identifying anomalous changes to the DNS records that may be indicative of possible DNS hijacking. According to one embodiment, DNS monitoring engine running on a network security appliance protecting a private network, or implemented as a cloud-based service can be used for monitoring DNS records of the entity. Any modification in the monitored DNS record(s) can be detected within a pre-defined or configurable time-frame. The detected modification can be determined to be anomalous or not, by assigning a criticality value based on current value and previous value of one or more fields of the DNS record, one or more attributes of the DNS record and one or more derived attributes based on the DNS record.