One embodiment of the present invention provides a dynamic overlay tunnel orchestration system. During operation, the system detects the appearance of a first virtual machine running on a hypervisor of a first host machine coupled to a first switch in a network. The system identifies a first virtual local area network (VLAN) associated with the first virtual machine and determines whether an overlay tunnel exists between the first switch and a second switch coupling a second virtual machine belonging to the first VLAN. If no such overlay tunnel exists, the system generates an instruction for the first and second switches to establish a first overlay tunnel between the first and second switches.