Step counting (SC) algorithms can be applied to different areas such as well-being applications, games, and indoor navigation. Many existing SC algorithms for smartphones use data from inertial sensors to infer the number of steps taken, but their usefulness in real-life situations is limited since typically only a few positions and orientations are supported. Moreover, the algorithms may suffer from dynamic orientation and position changes during walking. To alleviate these shortcomings, we propose the Position and Orientation Independent Step Counting Algorithm (POISCA), which uses an accelerometer and a gyroscope to count the number of steps while allowing the smartphone’s position and orientation to change dynamically. In a nutshell, the algorithm first determines the orientation of the smartphone, and then detects zero crossings with a predetermined buffer range. 48 young adults (36 males, 12 females) participated in an experiment that simulated a real-life scenario to evaluate the performance of POISCA against three other step counting algorithms. The data from 24 participants were randomly assigned to a training group, which was then used to establish threshold parameters for POISCA. The remaining 24 participants’ data were used for accuracy measurement. The results show that POISCA outperforms the other algorithms with a Symmetric Mean Absolute Percentage Error of 4.54%, which can be lower if the algorithm is calibrated for each user. The results suggest that POISCA has potential for use in real-life situations where changes in position and orientation of the smartphone are dynamic.