HIV testing and counselling forms the gateway to the HIV care and treatment continuum. Therefore, the World Health Organization recommends provider-initiated testing and counselling (PITC) in countries with a generalized HIV epidemic. Few studies have investigated linkage-to-HIV-care among out-patients after PITC. Our objective was to study timely linkage-to-HIV-care in six Rwandan health facilities (HFs) before and after the introduction of PITC in the out-patient departments (OPDs). Information from patients diagnosed with HIV was abstracted from voluntary counselling and testing, OPD and laboratory registers of six Rwandan HFs during three-month periods before (March-May 2009) and after (December 2009-February 2010) the introduction of PITC in the OPDs of these facilities. Information on patients' subsequent linkage-to-pre-antiretroviral therapy (ART) care and ART was abstracted from ART clinic registers of each HF. To triangulate the findings from HF routine, a survey was held among patients to assess reasons for non-enrolment. Of 635 patients with an HIV diagnosis, 232 (36.5%) enrolled at the ART clinic within 90 days of diagnosis. Enrolment among out-patients decreased after the introduction of PITC (adjusted odds ratio, 2.0; 95% confidence interval, 1.0-4.2; p = .051). Survey findings showed that retesting for HIV among patients already diagnosed and enrolled into care was not uncommon. Patients reported non-acceptance of disease status, stigma and problems with healthcare services as main barriers for enrolment. Timely linkage-to-HIV-care was suboptimal in this Rwandan study before and after the introduction of PITC; the introduction of PITC in the OPD may have had a negative impact on linkage-to-HIV-care. Healthier patients tested through PITC might be less ready to engage in HIV care. Fear of HIV stigma and mistrust of test results appear to be at the root of these problems.