Borneo Island is experiencing rapid tree-cover loss. This loss has been quantified for the Indonesian part of the island at Landsat spatial resolution, but no recent study exists that extends across the border into Malaysia. This research focused on quantifying patterns of tree-cover loss in the Indonesia–Malaysia border zone on Borneo. The methods used for quantifying 2000–2010 tree-cover loss within 20 km on either side of the border are an internally consistent mapping algorithm used on Landsat imagery and a local indicator of spatial autocorrelation to quantify the concentration of loss. Within the 20 km zone on either side of the border, tree-cover loss rates in lowlands were high in the two countries (19.8% and 14.4%, in Indonesia and Malaysia, respectively), but rates in the Malaysian uplands were an order of magnitude higher than in the Indonesian uplands (2.95% and 0.25%, respectively). Clusters of tree-cover loss in the Malaysian uplands were considerably larger than in the Indonesian uplands.