The re-emergence of tuberculosis (TB) in the mid-1980s in many parts of the world, including the United States, is often attributed to the emergence and rapid spread of human immunodeficiency virus (HIV) and acquired immunodeficiency syndrome (AIDS). Although it is well established that TB transmission is particularly amplified in populations with high HIV prevalence, the epidemiology of interaction between TB and HIV is not well understood. This is partly due to the scarcity of HIV-related data, a consequence of the voluntary nature of HIV status reporting and testing, and partly due to current practices of screening high risk populations through separate surveillance programs for HIV and TB. The San Francisco Department of Public Health, TB Control Program, has been conducting active surveillance among the San Francisco high-risk populations since the early 1990s. We present extensive TB surveillance data on HIV and TB infection among the San Francisco homeless to investigate the association between the TB cases and their HIV+ contacts. We applied wavelet coherence and phase analyses to the TB surveillance data from January 1993 through December 2005, to establish and quantify statistical association and synchrony in the highly non-stationary and ostensibly non-periodic waves of TB cases and their HIV+ contacts in San Francisco. When stratified by homelessness, we found that the evolution of TB cases and their HIV+ contacts is highly coherent over time and locked in phase at a specific periodic scale among the San Francisco homeless, but no significant association was observed for the non-homeless. This study confirms the hypothesis that the dynamics of HIV and TB are significantly intertwined and that HIV is likely a key factor in the sustenance of TB transmission among the San Francisco homeless. The findings of this study underscore the importance of contact tracing in detection of HIV+ individuals that may otherwise remain undetected, and thus highlights the ever-increasing need for HIV-related data and an integrative approach to monitoring high-risk populations with respect to HIV and TB transmission.