RNA-protein interactions govern many viral and host cell processes. Conventional 'footprinting' to examine RNA-protein complex formation often cannot distinguish between sites of RNA-protein interaction and sites of RNA structural remodelling. We have developed a novel technique combining photo crosslinking with RNA 2' hydroxyl reactivity ('SHAPE') that achieves rapid and hitherto unachievable resolution of both RNA structural changes and the sites of protein interaction within an RNA-protein complex. 'XL-SHAPE' was validated using well-characterized viral RNA-protein interactions: HIV-1 Tat/TAR and bacteriophage MS2 RNA/Coat Binding Protein. It was then used to map HIV-1 Gag protein interactions on 2D and 3D models of the viral RNA leader. Distinct Gag binding sites were identified on exposed RNA surfaces corresponding to regions identified by mutagenesis as important for genome packaging. This widely applicable technique has revealed a first view of the stoichiometry and structure of the initial complex formed when HIV captures its genome.