RNA deaminases are powerful tools for base editing and RNA molecular recording. However, the enzymes used in currently available RNA molecular recorders such as TRIBE, DART or STAMP have limitations due to RNA structure and sequence dependence. We designed a platform for directed evolution of RNA molecular recorders. We engineered an RNA A-to-I deaminase (an RNA adenosine base editor, rABE) that has high activity, low bias and low background. Using rABE, we present REMORA (RNA-encoded molecular recording in adenosines), wherein deamination by rABE writes a molecular record of RNA-protein interactions. By combining rABE with the C-to-U deaminase APOBEC1 and long-read RNA sequencing, we measured binding by two RNA-binding proteins on single messenger RNAs. Orthogonal RNA molecular recording of mammalian Pumilio proteins PUM1 and PUM2 shows that PUM1 competes with PUM2 for a subset of sites in cells. Furthermore, we identify transcript isoform-specific RNA-protein interactions driven by isoform changes distal to the binding site. The genetically encodable RNA deaminase rABE enables single-molecule identification of RNA-protein interactions with cell type specificity.