Transverse magnetohydrodynamic (MHD) waves have been shown to be ubiquitous in the solar atmosphere and can in principle carry sufficient energy to generate and maintain the Sun's million-degree outer atmosphere or corona. However, direct evidence of the dissipation process of these waves and subsequent heating has not yet been directly observed. Here we report on high spatial, temporal, and spectral resolution observations of a solar prominence that show a compelling signature of so-called resonant absorption, a long hypothesized mechanism to efficiently convert and dissipate transverse wave energy into heat. Aside from coherence in the transverse direction, our observations show telltale phase differences around 180 degrees between transverse motions in the plane-of-sky and line-of-sight velocities of the oscillating fine structures or threads, and also suggest significant heating from chromospheric to higher temperatures. Comparison with advanced numerical simulations support a scenario in which transverse oscillations trigger a Kelvin-Helmholtz instability (KHI) at the boundaries of oscillating threads via resonant absorption. This instability leads to numerous thin current sheets in which wave energy is dissipated and plasma is heated. Our results provide direct evidence for wave-related heating in action, one of the candidate coronal heating mechanisms. ; Comment: 28 pages, 9 figures, accepted for publication in ApJ. Part II by Patrick Antolin et al. will appear soon