Strong many-body interaction in two-dimensional transitional metal dichalcogenides provides a unique platform to study the interplay between different quasiparticles, such as prominent phonon replica emission and modified valley-selection rules. A large out-of-plane magnetic field is expected to modify the exciton-phonon interactions by quantizing excitons into discrete Landau levels, which is largely unexplored. Here, we observe the Landau levels originating from phonon-exciton complexes and directly probe exciton-phonon interaction under a quantizing magnetic field. Phonon-exciton interaction lifts the inter-Landau-level transition selection rules for dark trions, manifested by a distinctively different Landau fan pattern compared to bright trions. This allows us to experimentally extract the effective mass of both holes and electrons. The onset of Landau quantization coincides with a significant increase of the valley-Zeeman shift, suggesting strong many-body effects on the phonon-exciton interaction. Our work demonstrates monolayer WSe2 as an intriguing playground to study phonon-exciton interactions and their interplay with charge, spin, and valley.