HIV-1 subtype D is associated with faster disease progression compared with subtype A. Immunological correlates of this difference remain undefined. We investigated invariant natural killer T (iNKT) cells and FoxP3+ regulatory T cells (Tregs) in Ugandans infected with either subtype. Loss of iNKT cells was pronounced in subtype D, whereas Tregs displayed more profound loss in subtype A infection. The iNKT cell levels were associated with CD4 T-cell interleukin-2 production in subtype A, but not in D, infection. Thus, these viral subtypes are associated with differential loss of iNKT cells and Tregs that may influence the quality of the adaptive immune response.