Learning-based classification dominates malware detectors for Android. However, due to the evolution of the Android ecosystem, existing such techniques are limited by their reliance on new malware samples, which may not be timely available, and constant retraining, which are often costly. A practical detector needs not only to be accurate on particular datasets but, more critically, to be able to sustain its capabilities over time without frequent retraining. We propose and study the sustainability problem for learning-based app classifiers. We define sustainability metrics and compare them among five state-of-the-art malware detectors. We further developed DroidSpan, a novel classification system based on a new behavioral profile that capture sensitive access distribution. We evaluated the sustainability of DroidSpan versus the five detectors on longitudinal datasets across eight years, which include 13,627 benign apps and 12,755 malware. We showed that DroidSpan significantly outperformed these baselines in sustainability at reasonable costs, by 6–32% for same-period detection and 21–37% for over-time detection. The main takeaway, which also explains the superiority of DroidSpan, is that the use of features consistently differentiating malware from benign apps over time is essential for sustainable learning-based malware detection, and that these features can be learned from app evolution studies.