This paper presents a new approach for estimating burned areas at a regional scale, using a systematic sample of medium spatial resolution satellite images. This approach is based on a pan-tropical deforestation survey developed by the Joint Research Centre. We developed and tested our approach over Mato Grosso State, located in the Brazilian Legal Amazon region, with a total area of 903,366 km². We analyze Landsat-5 TM imagery over 77 sample sites (20 km × 20 km in size) located at each full degree confluence of latitude and longitude. Our new approach leads to an estimate of burned area for year 2010 at 66,368 km², representing approximately 7.3% of the Mato Grosso area. This estimate is compared to estimates from two different approaches: (i) from a method developed by the Brazilian Institute for Space Research, applied to a wall-to-wall coverage of Landsat-5 TM imagery and (ii) from a method using MODIS MCD64A1 products of the University of Maryland, resulting in 70,232 km² and 55,157 km² of burned area respectively (representing 7.8% or 6.1% of Mato Grosso area). Our method produces statistically valid estimates of burned areas for the Brazilian State of Mato Grosso in a more efficient manner than previous methods and enables the inclusion of small burn scars typically missed by coarse resolution satellites. This approach can be applied for regional and global assessments as well as for refining and evaluating burned area products based on coarse spatial resolution imagery like MODIS or SPOT-VEGETATION.