With the rate at which smartphones are currently evolving, more and more of human life will be contained in these devices. At a time when data privacy is extremely important, it is crucial to protect one’s mobile device. In this paper, we propose a new non-intrusive gait recognition based mechanism that can enhance the security of smartphones by rapidly identifying users with a high degree of confidence and securing sensitive data in case of an attack, with a focus on a potential architecture for such an algorithm for the Android environment. The motion sensors on an Android device are used to create a statistical model of a user’s gait, which is later used for identification. Through experimental testing, we prove the capability of our proposed solution by correctly classifying individuals with an accuracy upwards of 90% when tested on data recorded during multiple activities. The experiments, conducted on a low sampling rate and at short time intervals, show the benefits of our solution and highlight the feasibility of an efficient gait recognition mechanism on modern smartphones.