In this paper, we propose covariogram-based compressive sensing (CB-CS), a spatio-temporal compression algorithm for environmental wireless sensor networks. CB-CS combines a novel sampling mechanism along with an original covariogram-based approach for the online estimation of the covariance structure of the signal and leverages the signal’s spatio-temporal correlation structure through the Kronecker CS framework. CB-CS’s performance is systematically evaluated in the presence of synthetic and real signals, comparing it against a number of compression methods from the literature, based on linear approximations, Fourier transforms, distributed source coding, and against several approaches based on CS. CB-CS is found superior to all of them and able to effectively and promptly adapt to changes in the underlying statistical structure of the signal, while also providing compression versus energy tradeoffs that approach those of idealized CS schemes (where the signal correlation structure is perfectly known at the receiver).