Indoor pedestrian localization is of great importance for diverse mobile applications. Many indoor localization approaches have been proposed; among them, Radio Signal Strength (RSS)-based approaches have the advantage of existing infrastructures and avoid the cost of infrastructure deployment. However, the RSS-based localization approaches suffer from poor localization accuracy when the RSS fingerprints are sparse, as illustrated by actual experiments in this study. Here, we propose a novel indoor pedestrian tracking approach for smartphone users; this approach provides a high localization accuracy when the RSS fingerprints are sparse. Besides using the RSS fingerprints, this approach also utilizes the inertial sensor readings on smartphones. This approach has two components: (i) dead-reckoning subsystem that counts the number of walking steps with off-the-shelf inertial sensor readings on smartphones and (ii) particle filtering that computes the locations with only sparse RSS readings. The proposed approach is implemented on Android-based smartphones. Extensive experiments are carried out in both small and large testbeds. The evaluation results show that the tracking approach can achieve a high accuracy of 5 m (up to 95%) in indoor environments with only sparse RSS fingerprints.