Accurate step counting is essential for indoor positioning, health monitoring systems, and other indoor positioning services. There are several publications and commercial applications in step counting. Nevertheless, over-counting, under-counting, and false walking problems are still encountered in these methods. In this paper, we propose to develop a highly accurate step counting method to solve these limitations by proposing four features: Minimal peak distance, minimal peak prominence, dynamic thresholding, and vibration elimination, and these features are adaptive with the user’s states. Our proposed features are combined with periodicity and similarity features to solve false walking problem. The proposed method shows a significant improvement of 99.42% and 96.47% of the average of accuracy in free walking and false walking problems, respectively, on our datasets. Furthermore, our proposed method also achieves the average accuracy of 97.04% on public datasets and better accuracy in comparison with three commercial step counting applications: Pedometer and Weight Loss Coach installed on Lenovo P780, Health apps in iPhone 5s (iOS 10.3.3), and S-health in Samsung Galaxy S5 (Android 6.01).