Monitoring large forest areas is presently feasible with satellite remote sensing as opposed to time-consuming and expensive ground surveys as alternative. This study evaluated, for the first time, the potential of using freely available medium resolution (30 m) Landsat time series data for deforestation monitoring in tropical rainforests of Kalimantan, Indonesia, at sub-annual time scales. A simple, generic, data-driven algorithm for deforestation detection based on a consecutive anomalies criterion was proposed. An accuracy assessment in the spatial and the temporal domain was carried out using high-confidence reference sample pixels interpreted with the aid of multi-temporal very high spatial resolution image series. Results showed a promising spatial accuracy, when three consecutive anomalies were required to confirm a deforestation event. Recommendations in tuning the algorithm for different operational use cases were provided within the context of satisfying REDD+ requirements, depending on whether spatial accuracy or temporal accuracy need to be optimized.