Indoor localization using signal strength in Wireless Local Area Networks is becoming increasingly prevalent in today’s pervasive computing applications. In this paper, we propose an indoor tracking algorithm under the Bayesian filtering and machine learning framework. The main idea is to apply a graph-based particle filter to track a person’s location on an indoor floor map, and to utilize the machine learning method to approximate the likelihood of an observation at various locations based on the calibration data. Histograms are used to approximate the RSS distributions at the survey points, and Nadaraya–Watson kernel regression is adopted to recover the distributions at non-survey points only from the nearby locations. In addition, we also propose a simple algorithm to continuously update the radio map with the online measurements. A series of experiments are carried out in an office environment. Results show that the proposed Histogram Based Particle Filtering (HBPF)/HBPF with Online Adaptation achieves superior performance than other existing algorithms while retaining low computational complexity.