Eastern Rwanda consists of a mosaic of different land cover types, with agroforestry, forest patches, and shrubland all containing tree cover. Mapping and monitoring the landscape is costly and time-intensive, creating a need for automated methods using openly available satellite imagery. Google Earth Engine and the random forests algorithm offer the potential to use such imagery to map tree cover types in the study area. Sentinel-2 satellite imagery, along with vegetation indices, texture metrics, principal components, and non-spectral layers were combined over the dry and rainy seasons. Different combinations of input bands were used to classify land cover types in the study area. Recursive feature elimination was used to select the most important input features for accurate classification, with three final models selected for classification. The highest classification accuracies were obtained for the forest class (85–92%) followed by shrubland (77–81%) and agroforestry (68–77%). Agroforestry cover was predicted for 36% of the study area, forest cover was predicted for 14% of the study area, and shrubland cover was predicted for 18% of the study area. Non-spectral layers and texture metrics were among the most important features for accurate classification. Mixed pixels and fragmented tree patches presented challenges for the accurate delineation of some tree cover types, resulting in some discrepancies with other studies. Nonetheless, the methods used in this study were capable of delivering accurate results across the study area using freely available satellite imagery and methods that are not costly and are easy to apply in future studies.