Abstract: In the recent years, there has been an exponential growth in the number of malware captured and analyzed by the antivirus companies. However, much of these malwares are variants of already known malware. Thus, it has become necessary to determine whether a malware belongs to a known family, or exhibits a new behavior hitherto unseen, and requires further analysis. Existing traditional approaches used by antivirus companies are based on signature-based detection and can be thwarted in case of zero-day exploit-based malware. Manual examination of such executables is extremely cumbersome due to the enormous number of such cases. Also, it has become necessary to speed up the detection process and predict before the executable releases its malicious payload. In this work, we addressed all the above issues using automated yet efficient malware analysis. We classified the malicious executables into different malware classes in the earliest possible time using dynamic analysis. Dynamic analysis provides useful insights in the case of obfuscated or packed malware where static analysis fails. Our experiments achieve an accuracy of 98.02% for classifying malware into classes in the initial 4 seconds of its execution using XGBoost. We also classified samples which were not seen by the classifier before, thus attempted to classify zero-day malware. Our solution is robust and scalable as we have increased the number of samples used during analysis compared to prior work and reduced the execution time drastically. Our solution is also efficient since the state of the art accuracy for early stage malware detection is 91% for the first 4 seconds of execution and 96% for the first 19 seconds using recurrent neural networks.