In-depth study of mechanisms of immune response to the human immunodeficiency virus (HIV) is critical for better understanding of how immunodeficiency develops in patients with HIV, as well as for designing effective immunotherapy strategies and vaccines against the virus. In this work we analyze sequencing profiles of T-cell receptor repertoires previously obtained from healthy donors (601 Americans and 65 Russians) to estimate the population frequency of HIV-specific naive T-cells. We demonstrate that frequencies of T-cells recognizing different HIV epitopes vary considerably across the population (F-statistic = 2007, p < 10^–100, ANOVA). Although the frequency of T-lymphocytes recognizing a particular epitope does not change significantly between the individuals, it still largely depends on the presence of certain HLA alleles (p < 0.01, post-hoc Tukey’s test), cytomegalovirus infection (F = 61, p = 7 × 10–15, ANOVA), and age (Pearson correlation coefficient ranging from –0.53 to –0.14 in different groups).