Astrophysical searches for new long-range interactions complement collider searches for new short-range interactions. Conveniently, neutrino flavor oscillations are keenly sensitive to the existence of long-ranged flavored interactions between neutrinos and electrons, motivated by lepton-number symmetries of the Standard Model. For the first time, we probe them using TeV-PeV astrophysical neutrinos and accounting for all large electron repositories in the local and distant Universe. The high energies and colossal number of electrons grant us unprecedented sensitivity to the new interaction, even if it is extraordinarily feeble. Based on IceCube results for the flavor composition of astrophysical neutrinos, we set the ultimate bounds on long-range neutrino flavored interactions.