Network Address Translation (NAT) is a technique commonly employed in today’s computer networks. NAT allows multiple devices to hide behind a single IP address. From a network management and security point of view, NAT may not be desirable or permitted as it allows rogue and unattended network access. In order to detect rogue NAT devices, we propose a novel passive remote source NAT detection approach based on behavior statistics derived from NetFlow. Our approach utilizes 9 distinct features that can directly be derived from NetFlow records. Furthermore, our approach does not require IP address information, but is capable of operating on anonymous identifiers. Hence, our approach is very privacy friendly. Our approach requires only a 120 seconds sample of NetFlow records to detect NAT traffic within the sample with a lower-bound accuracy of 89.35%. Furthermore, our approach is capable of operating in real-time.