Density estimation is an important technique in stream mining for a wide variety of applications. The construction of kernel density estimators is well studied and documented. However, existing techniques are either expensive or inaccurate and unable to capture the changes in the data distribution. In this paper, we present a method called KDE-Track to estimate the density of spatiotemporal data streams. KDE-Track can efficiently estimate the density function with linear time complexity using interpolation on a kernel model, which is incrementally updated upon the arrival of new samples from the stream. We also propose an accurate and efficient method for selecting the bandwidth value for the kernel density estimator, which increases its accuracy significantly. Examples of data streams can be found in fields such as sensor networks, mobile data collection platform, and network traffic. The data need to be processed and analyzed once they arrive. However, the unbounded, rapid and continuous arrival of data streams disallow the usage of traditional data mining techniques. Therefore, the development of algorithms for processing data streams instantaneously becomes highly important. Density estimation has been widely used in various applications. Estimating the Probability Density Function (PDF) for a given data set provides knowledge about the underlying distribution of the data. Consequently, dense regions can be recognized as clusters and quantities such as medians and centers of clusters can be computed. By contrast, sparse regions are reported as outliers that can be used for fault detection, e.g., in sensor networks.