Load balancing is an integrated aspect of cloud computing. In order to achieve optimal machine utilization, tasks from overloaded virtual machines have to be transferred to under loaded virtual machines. In this paper, the honey bee foraging mechanism for load balancing is improved by random stealing technique. For finding the state of a virtual machine, the deviation of virtual machine load is calculated and checked for confinement within a threshold condition set. With random stealing method, tasks are stolen from a random Virtual machine when a VM is idle.