Datasets from remote-sensing platforms and sensor networks are often spatial, temporal, and very large. Processing massive amounts of data to provide current estimates of the (hidden) state from current and past data is challenging, even for the Kalman filter. A large number of spatial locations observed through time can quickly lead to an overwhelmingly high-dimensional statistical model. Dimension reduction without sacrificing complexity is our goal in this article. We demonstrate how a Spatio-Temporal Random Effects (STRE) component of a statistical model reduces the problem to one of fixed dimension with a very fast statistical solution, a methodology we call Fixed Rank Filtering (FRF). This is compared in a simulation experiment to successive, spatialonly predictions based on an analogous Spatial Random Effects (SRE) model, and the value of incorporating temporal dependence is quantified. A remote-sensing dataset of aerosol optical depth (AOD), from the Multi-angle Imaging SpectroRadiometer (MISR) instrument on the Terra satellite, is used to compare spatio-temporal FRF with spatialonly prediction. FRF achieves rapid production of optimally filtered AOD predictions, along with their prediction standard errors. In our case, over 100,000 spatio-temporal data were processed: Parameter estimation took 64.4 seconds and optimal predictions and their standard errors took 77.3 seconds to compute. Supplemental materials giving complete details on the design and analysis of a simulation experiment, the simulation code, and the MISR data used are available on-line. © 2010 American Statistical Association, Institute of Mathematical Statistics, and Interface Foundation of North America.