The persistence of tropical rainforests, together with their flora and fauna, is highly threatened by anthropogenic disturbances. In this study, we investigate to what extent selective logging influences the structure and composition of a tropical rainforest in Madagascar and subsequently lemur encounter rates and cluster sizes. We quantified forest structure variables and conducted transect surveys of seven sympatric diurnal lemur species in five protected forest sites with different logging histories. We found that DBH, tree height, the interquartile ranges of DBH and tree height (measure of forest heterogeneity), tree species and family richness were relatively high and tree density was relatively low in less disturbed compared to disturbed sites. Although the disturbed forests have not fully recovered to previous conditions, they seem to have recovered from a functional perspective into suitable lemur habitat, as lemur encounter rates and cluster sizes were similar in disturbed and less disturbed sites. We only found slightly higher encounter rates for Varecia variegata (P = 0.078) and lower encounter rates for Eulemur rufifrons (P = 0.059) in less disturbed forests. This is one of the first studies that report the presence of V. variegata, a species characterised by its drastic decline, in previously logged sites. Lemurs travelling between disturbed and less disturbed sites disperse seeds and hereby facilitate forest regeneration. Therefore, we promote the need for better attention to the value of logged forests for biodiversity conservation in Madagascar and suggest that there is considerable potential for regenerating logged forests to support lemur communities.