High affinity RNA-protein interactions are critical to cellular function, but directly identifying the determinants of binding within these complexes is often difficult. Here, we introduce a stable isotope mass labeling technique to assign specific interacting nucleotides in an oligonucleotide-protein complex by photo-cross-linking. The method relies on generating site-specific oxygen-18-labeled phosphodiester linkages in oligonucleotides, such that covalent peptide-oligonucleotide cross-link sites arising from ultraviolet irradiation can be assigned to specific sequence positions in both RNA and protein simultaneously by mass spectrometry. Using Lin28A and a let-7 pre-element RNA, we demonstrate that mass labeling permits unambiguous identification of the cross-linked sequence positions in the RNA-protein complex.