Verification of Internet connectivity using multiple prior connection attempts to Internet destination(s). The Internet destinations may be destinations that have high reliability and that do not easily have intermediating systems that might deny a connection request. Such an Internet destination might be, for example, root Domain Name Server (DNS) servers. Connection attempt results are obtained by for at least some of the connection attempts, tracking which resulted in success and failure. Internet connectivity is then verified based on the collective results, rather than relying on any one single connection attempt. In one embodiment, the frequency of the connection attempts may depend on a current state of the Internet connection.