Over the past few years, Android has become one of the most popular operating systems for smartphones as it is open-source and provides extensive support for wide variety of applications. This has led to an increase in the number of malware targeting Android devices. The lack of robust security enforcement in Play Store along with the rapid increase in the number of new Android malware presents a scope for a variety of diverse malicious applications to spread across devices. Furthermore, Android allows installation of an application from unverified sources (e.g., third-party market and sideloading), which opens up other ways for malware to infect the smartphones. This paper presents DeepDetect that enables on-device malware detection by employing a machine learning based model on static features. With effective feature engineering, DeepDetect can be used on-device. To classify an Android application as malware, it takes ∼5.32 seconds, which is 2.23X faster than API based malware detector, while consuming 0.45% (for 50 applications) of total device energy. DeepDetect provides a malware detection rate of 99.9% for known malware with a 0.01% false-positive rate. For unseen/new samples, it detects more than 97% malware with a false-positive rate of 1.73%. Further, in the presence of obfuscated malware, DeepDetect correctly detects 95.57% of malware samples. We have also evaluated our model against the Pegasus malware sample and with a new dataset after removing the potential biases across space and time.