Epidemiologic and clinical changes in the HIV epidemic over time have presented a challenge to public health surveillance to monitor behavioral and clinical factors that affect disease progression and HIV transmission. The Medical Monitoring Project (MMP) is a supplemental surveillance project designed to provide representative, population-based data on clinical status, care, outcomes, and behaviors of HIV-infected persons receiving care at the national level. We describe a three-stage probability sampling method that provides both nationally and state-level representative estimates. In stage-I, 20 states, which included 6 separately funded cities/counties, were selected using probability proportional to size (PPS) sampling. PPS sampling was also used in stage-II to select facilities for participation in each of the 26 funded areas. In stage-III, patients were randomly selected from sampled facilities in a manner that maximized the possibility of having overall equal selection probabilities for every patient in the state or city/county. The sampling methods for MMP could be adapted to other research projects at national or sub-national levels to monitor populations of interest or evaluate outcomes and care for a range of specific diseases or conditions.