Detection of vancomycin-resistant Enterococcus faecium (VRE) is hampered by low sensitivity of rectal swab cultures. This study aimed to define the number of screening cultures needed to increase sensitivity to detect VRE transmission, and to determine time from presumed exposure to detectable colonization. In a tertiary care setting, we retrospectively analyzed data from 9 VRE outbreaks. As a proxy or estimation for time to detectable colonization, the time between first positive culture of the presumed index patient and that of their contacts was determined. Only 64% of secondary cases were positive in the first out of five cultures. By using the first three out of five rectal swabs, 89% (95%CI: 78–95%) of all secondary cases would have been identified. The median number of days between the positive culture of the index patient and the first positive culture of secondary cases was 9 days. Eleven percent of secondary cases would have been missed if only three rectal samples would have been obtained. Furthermore, our results show that one or more rectal swabs taken around day 9 after presumed exposure should at least be included in the screening approach. In our setting, obtaining a fourth and a fifth rectal swab showed a relevant additional value compared to only one to three swabs. Our findings are useful for determining the most effective VRE contact tracing approach to prevent transmission.