Early initiation of antiretroviral therapy has been shown to reduce mortality among perinatally HIV-infected infants, but availability of virologic testing remains limited in many settings. We collected cross-sectional data from mother-infant pairs in three primary care clinics in Lusaka, Zambia, to develop predictive models for HIV infection among infants younger than 12 weeks of age. We evaluated algorithm performance for all possible combinations of selected characteristics using an iterative approach. In primary analysis, we identified the model with the highest combined sensitivity and specificity. Between July 2009 and May 2011, 822 eligible HIV-infected mothers and their HIV-exposed infants were enrolled; of these, 44 (5.4%) infants had HIV diagnosed. We evaluated 382,155,260 different characteristic combinations for predicting infant HIV infection. The algorithm with the highest combined sensitivity and specificity required 5 of the following 7 characteristic thresholds: infant CD8 percentage >22; infant CD4 percentage ≤44; infant weight-for-age Z score ≤0; infant CD4 ≤1600 cells/µL; infant CD8 >2200 cells/µL; maternal CD4 ≤600 cells/µL; and mother not currently using antiretroviral therapy for HIV treatment. This combination had a sensitivity of 90.3%, specificity of 78.4%, positive predictive value of 22.4%, negative predictive value of 99.2% and area under the curve of 0.844. Predicting HIV infection in HIV-exposed infants in this age group is difficult using clinical and immunologic characteristics. Expansion of polymerase chain reaction capacity in resource-limited settings remains urgently needed.