(1) Background: Waning of neutralizing and cell-mediated immune response after the primary vaccine cycle (PVC) and the first booster dose (BD) is of concern, especially for PLWH with a CD4 count ≤200 cells/mm3. (2) Methods: Neutralizing antibodies (nAbs) titers by microneutralization assay against WD614G/Omicron BA.1 and IFNγ production by ELISA assay were measured in samples of PLWH at four time points [2 and 4 months post-PVC (T1 and T2), 2 weeks and 5 months after the BD (T3 and T4)]. Participants were stratified by CD4 count after PVC (LCD4, ≤200/mm3; ICD4, 201–500/mm3, and HCD4, >500/mm3). Mixed models were used to compare mean responses over T1–T4 across CD4 groups. (3) Results: 314 PLWH on ART (LCD4 = 56; ICD4 = 120; HCD4 = 138) were enrolled. At T2, levels of nAbs were significantly lower in LCD4 vs. ICD4/HCD4 (p = 0.04). The BD was crucial for increasing nAbs titers above 1:40 at T3 and up to T4 for WD614G. A positive T cell response after PVC was observed in all groups, regardless of CD4 (p = 0.31). (4) Conclusions: Waning of nAbs after PVC was more important in LCD4 group. The BD managed to re-establish higher levels of nAbs against WD614G, which were retained for 5 months, but for shorter time for Omicron BA.1. The T cellular response in the LCD4 group was lower than that seen in participants with higher CD4 count, but, importantly, it remained above detectable levels over the entire study period.