The ability to efficiently establish a new infection is a critical property for human immunodeficiency virus type 1 (HIV-1). Although the envelope protein of the virus plays an essential role in receptor binding and internalization of the infecting virus, the structural proteins, the polymerase and the assembly of new virions may also play a role in establishing and spreading viral infection in a new host. We examined Ugandan viruses from newly infected patients and focused on the contribution of the Gag-Pol genes to replication capacity. A panel of Gag-Pol sequences generated using single genome amplification from incident HIV-1 infections were cloned into a common HIV-1 NL4.3 pol/env backbone and the influence of Gag-Pol changes on replication capacity was monitored. Using a novel protein domain approach, we then documented diversity in the functional protein domains across the Gag-Pol region and identified differences in the Gag-p6 domain that were frequently associated with higher in vitro replication.