High-energy tau neutrinos are rarely produced in atmospheric cosmic-ray showers or at cosmic particle accelerators, but are expected to emerge during neutrino propagation over cosmic distances due to flavor mixing. When high energy tau neutrinos interact inside the IceCube detector, two spatially separated energy depositions may be resolved, the first from the charged current interaction and the second from the tau lepton decay. We report a novel analysis of 7.5 years of IceCube data that identifies two candidate tau neutrinos among the 60 “High-Energy Starting Events” (HESE) collected during that period. The HESE sample offers high purity, all-sky sensitivity, and distinct observational signatures for each neutrino flavor, enabling a new measurement of the flavor composition. The measured astrophysical neutrino flavor composition is consistent with expectations, and an astrophysical tau neutrino flux is indicated at 2.8$\sigma $ significance.