Classification using machine learning has been a major class of defense solutions against malware. Yet in the presence of a large and growing number of learning-based malware detection techniques for Android, malicious apps keep breaking out, with an increasing momentum, in various Android app markets. In this context, we ask the question “what is it that makes new and emerging malware slip through such a great collection of detection techniques?”. Intuitively, performance deterioration of malware detectors could be a main cause—trained on older samples, they are increasingly unable to capture new malware. To understand the question, this work sets off to investigate the deterioration problem in four state-of-the-art Android malware detectors. We confirmed our hypothesis that these existing solutions do deteriorate largely and rapidly over time. We also propose a new classification approach that is built on the results of a longitudinal characterization study of Android apps with a focus on their dynamic behaviors. We evaluated this new approach against the four existing detectors and demonstrated significant advantages of our new solution. The main lesson learned is that studying app evolution provides a promising avenue for long-span malware detection.