The purpose of this report is to share key lessons learned from the implementation phase of EAST concerning study design, recruitment, and other practical and logistical issues integral to the success of a survey-based study in hard-to-reach populations. During the course of the study, formal and informal evaluation measures were employed in order to document challenges and subsequent solutions. Documenting these efforts became an objective of EAST because of the gaps in existing HIV research literature concerning research with African, Caribbean, and Black communities. This report is based on data extracted from a recruitment tracking database, on-going qualitative notations concerning the challenges we faced, and interviews with study research assistants and interviewers. It is our hope that the lessons we learned may be useful when designing and conducting future research with East African communities, other communities from countries where HIV is endemic, and other similar hard-to-reach populations.