Binding of APOBEC3G to the nucleocapsid (NC) domain of the human immunodeficiency virus (HIV) Gag polyprotein may represent a critical early step in the selective packaging of this antiretroviral factor into HIV virions. Previously, we and others have reported that this interaction is mediated by RNA. Here, we demonstrate that RNA binding by APOBEC3G is key for initiation of APOBEC3G:NC complex formation in vitro. By adding back nucleic acids to purified, RNase-treated APOBEC3G and NC protein preparations in vitro, we demonstrate that complex formation is rescued by short (> or =10 nucleotides) single-stranded RNAs (ssRNAs) containing G residues. In contrast, complex formation is not induced by add-back of short ssRNAs lacking G, by dsRNAs, by ssDNAs, by dsDNAs or by DNA:RNA hybrid molecules. While some highly structured RNA molecules, i.e., tRNAs and rRNAs, failed to rescue APOBEC3G:NC complex formation, other structured RNAs, i.e., human Y RNAs and 7SL RNA, did promote NC binding by APOBEC3G. Together, these results indicate that ternary complex formation requires ssRNA, but suggest this can be presented in the context of an otherwise highly structured RNA molecule. Given previous data arguing that APOBEC3G binds, and edits, ssDNA effectively in vitro, these data may also suggest that APOBEC3G can exist in two different conformational states, with different activities, depending on whether it is bound to ssRNA or ssDNA.