Botnets are an enabler for many cyber-criminal activities and often responsible for DDoS attacks, banking fraud, cyber-espionage and extortion. Botnets are controlled by a botmaster that uses various advanced techniques to create, maintain and hide their complex and distributed C&C infrastructures. First, they use P2P techniques and domain fast-flux to increase the resilience against take-down actions. Second, botnets encrypt their communication payload to prevent signature based detection. Both, the actions to increase the resilience and the prevention of signature based detection are counteractions against detection techniques. In contrast to existing approaches, our novel approach includes DNS registration behaviour, which we currently analyse for the .com, .net and .org domains, representing half of registered domains on the Internet. Hence, the goal of this PhD research is to enable early detection of the deployment and operation of botnets to facilitate proactive mitigation strategies, whereas current approaches usually detect botnets while these are already in active use. Consequently, this proactive approach prevents botnets to fully evolve their size and attack power. Moreover, as many end users are unable to detect and clean infected machines, our approach tackles the botnet phenomenon without requiring any end user involvement, by incorporating ISPs and domain name registrars. In addition, this will enable the discovery of similar behaviour of different connected systems, which allows detection in cases where bots are registered under domains that are not willing to cooperate.