A system and method for performing load balancing over an overlay network is disclosed. The load balancing is performed by a DNS load balancing module communicating to a plurality of computing devices communicatively coupled over the overlay network. The DNS load balancing module calculates and maintains a weighted value of each computing device among the plurality of computing device based on a plurality of parameters. The DNS load balancing module on receiving a DNS lookup request for a resource from a first computing device identifies a list of computing device among the plurality of computing device hosting the requested resource. The DNS load balancing module further performs load balancing by selecting a computing device among a list of computing devices for accessing the resource based on a weighted value calculated.