(1) Background: Prion-like transcellular spreading of tau pathology in Alzheimer’s disease (AD) is mediated by tau binding to the cell-surface glycan heparan sulfate (HS). However, the structural determinants for tau–HS interaction are not well understood. (2) Methods and Results: Binding-site mapping using NMR showed two major binding regions in full-length tau responsible for heparin interaction. Thus, two tau constructs, tau PRR2* and tau R2*, were designed to investigate the molecular details at the tau–heparin binding interface. The 2D 1H-15N HSQC of tau PRR2* and tau R2* lacked dispersion, which is characteristic for intrinsically disordered proteins. NMR titration of Arixtra into 15N-labeled tau R2* induced large chemical shift perturbations (CSPs) in 275VQIINK280 and downstream residues K281-D283, in which L282 and I278 displayed the largest shifts. NMR titration of Arixtra into 15N-labeled tau PRR2* induced the largest CSPs for residue R209 followed by residues S210 and R211. Residue-based CSP fitting showed that tau PRR2*–Arixtra interaction had a much stronger binding affinity (0.37–0.67 mM) than that of tau R2*–Arixtra (1.90–5.12 mM) interaction. (3) Conclusions: Our results suggested that PRR2 is a crucial domain for tau–heparin and tau–HS interaction.