A process capable of automatically establishing a secure overlay network (“SON”) across different clouds is disclosed. The process, in one aspect, receives a first request from a first node in a first cloud for establishing a SON. After receiving a second request for connecting to the SON from a second node in a second cloud, a first connection is established connecting between the first node and the second node utilizing a network security protocol such as Internet Protocol Security (“IPSec”). After receiving a third request for connecting to the SON from a third node in a third cloud, a second connection is used to connect between the first node and the third node. A third connection is used to connect between the second node and the third node. Each subsequent request for connecting to the SON from a new node results in new connections between the new node and each existing node in the SON forming a full-mesh.