Android is one of the most popular operating systems used in mobile devices. Its popularity also renders it a common target for attackers. We propose an efficient and accurate three-phase behavior-based approach for detecting and classifying malicious Android applications. In the proposed approach, the first two phases detect a malicious application and the final phase classifies the detected malware. The first phase quickly filters out benign applications based on requested permissions and the remaining samples are passed to the slower second phase, which detects malicious applications based on system call sequences. The final phase classifies malware into known or unknown types based on behavioral or permission similarities. Our contributions are three-fold: First, we propose a self-contained approach for Android malware identification and classification. Second, we show that permission requests from an Application are beneficial to benign application filtering. Third, we show that system call sequences generated from an application running inside a virtual machine can be used for malware detection. The experiment results indicate that the multi-phase approach is more accurate than the single-phase approach. The proposed approach registered true positive and false positive rates of 97% and 3%, respectively. In addition, more than 98% of the samples were correctly classified into known or unknown types of malware based on permission similarities.We believe that our findings shed some lights on future development of malware detection and classification.