Sampling strategies such as respondent-driven sampling (RDS) and time-location sampling (TLS) offer unique opportunities to access key populations such as men who have sex with men (MSM) and transgender women. Limited work has assessed implementation challenges of these methods. Overcoming implementation challenges can improve research quality and increase uptake of HIV services among key populations. Drawing from studies using RDS in Brazil and TLS in Peru, we summarize challenges encountered in the field and potential strategies to address them. In Brazil, study site selection, cash incentives, and seed selection challenged RDS implementation with MSM. In Peru, expansive geography, safety concerns, and time required for study participation complicated TLS implementation with MSM and transgender women. Formative research, meaningful participation of key populations across stages of research, and transparency in study design are needed to link HIV/AIDS research and practice. Addressing implementation challenges can close gaps in accessing services among those most burdened by the epidemic.