This study seeks to identify challenges in the implementation of post-exposure prophylaxis for HIV, based on an analysis of actions taken by healthcare professionals in the state-run health sector in Porto Alegre, Brazil. Based on a qualitative approach that included ethnographic observations and in-depth interviews, we found that contextual, institutional, and individual factors represented challenges to the implementation of post-exposure prophylaxis for HIV. Barriers to implementation included the historical context structuring healthcare services and practices, the lack of training and/or continued education in health, and certain attitudes on the part of healthcare professionals (ideas regarding both the strategy itself as well as the individuals that seek PEP). We conclude that there is a need for greater attention to specialized services for STI/HIV/AIDS as well as the professionals that provide these services, in order to guarantee greater effective access to this strategy at the local level.