The flavor composition of astrophysical neutrinos observed at neutrino telescopes is related to the initial composition at their sources via oscillation-averaged flavor transitions. If the time evolution of the neutrino flavor states is unitary, the probability of neutrinos changing flavor is solely determined by the unitary mixing matrix that relates the neutrino flavor and propagation eigenstates. In this paper we derive general bounds on the flavor composition of TeV-PeV astrophysical neutrinos based on unitarity constraints. These bounds are useful for studying the flavor composition of high-energy neutrinos, where energy-dependent nonstandard flavor mixing can dominate over the standard mixing observed in accelerator, reactor, and atmospheric neutrino oscillations.