Being connected to other people at the level of inner and unobservable mental states is one of the most essential aspects of a meaningful life, including psychological well-being and successful cooperation. The foundation for this kind of connectedness is our theory of mind (ToM), that is the ability to understand our own and others' inner experiences in terms of mental states such as beliefs and desires. But how do we develop this ability? Forty-six 17- to 107-months-old children completed a non-verbal eye-tracker false-belief task. There were 9 signing deaf children from deaf families and two comparison groups, that is 13 deaf children with cochlear implants and 24 typically developing hearing children. We show that typically developing hearing children and deaf children from deaf families, but not deaf children with cochlear implants, succeeded on a non-verbal eye-tracking ToM task. The findings suggest that the ability to recognize others' mental states is supported by very early, continuous and fluent language-based communication with caregivers.