Video calling devices are described herein that are configured to exchange video presence statuses with each other. Each of these video calling devices determines its presence status based at least on its network connection type, its login status for a video calling service, and its camera status and provides the presence status to the video calling service. Each video calling device also receives presence statuses of other video calling devices. This exchange of presence statuses enables initiation of video calls between the video calling devices.