Routine 'provider-initiated testing and counselling' (PITC) for HIV has been implemented amidst concern over how consent, confidentiality and counselling (the 3C’s) can be maintained in underresourced health care settings. In Kenya, PITC has been rolled out since 2005, HIV prevalence is 7.1% and over 86% of adults have not been tested. Kenyan nurses are the main cadre implementing PITC but little is known about their experiences of incorporating HIV testing into everyday practice and the challenges faced in maintaining the 3’Cs within their work environments. This study aimed to explore these issues and adopted a qualitative multi-method design using a convenience sampling approach. Two focus group discussions (total n=12) and 13 in-depth individual interviews were undertaken with nurses from 11 different public health care facilities in Nairobi and its surrounding areas (including in- and out-patient settings). Data were analysed thematically. Nurses identified a range of personal, client and health system challenges in the everyday application of PITC. These included: (i) the contradictions of normalising a highly stigmatised disease and the difficulty of providing client centred care within a routinised and target oriented work culture; (ii) the challenge of dealing with ethically complex client situations in which the principles of the 3C’s could be difficult to uphold; and, (iii) lack of time, resources, space and recognition within workplace environments (especially in-patient settings) that, likewise, led to problems with maintaining the 3C’s. In-patient nurses in particular identified problems associated with testing in a multi-disciplinary context, suggesting that other health professionals appeared to routinely flout the PITC guidelines. In conclusion, this study shows that the process of translating policy into practice is invariably complex and that more research is needed to explore PITC practices, particularly in in-patient settings. Nurses require supervision and support to negotiate the challenges and to fulfil their roles effectively.