A significant methodological challenge in implementing community-based cluster-randomized trials is how to accurately categorize cluster residency when data are collected at a site distant from households. This study set out to validate a map book system for use in urban slums with no municipal address systems, where classification has been shown to be inaccurate when address descriptions were used. Between April and July 2011, 28 noncontiguous clusters were demarcated in Blantyre, Malawi. In December 2011, antiretroviral therapy initiators were asked to identify themselves as cluster residents (yes/no and which cluster) by using map books. A random sample of antiretroviral therapy initiators was used to validate map book categorization against Global Positioning System coordinates taken from participants' households. Of the 202 antiretroviral therapy initiators, 48 (23.8%) were categorized with the map book system as in-cluster residents and 147 (72.8%) as out-of-cluster residents, and 7 (3.4%) were unsure. Agreement between map books and the Global Positioning System was 100% in the 20 adults selected for validation and was 95.0% (κ = 0.96, 95% confidence interval: 0.84, 1.00) in an additional 20 in-cluster residents (overall κ = 0.97, 95% confidence interval: 0.90, 1.00). With map books, cluster residents were classified rapidly and accurately. If validated elsewhere, this approach could be of widespread value in that it would enable accurate categorization without home visits.