Skype uses the concept of Supernodes, that relay communications on behalf of two clients. The Skype user directory is decentralized and distributed among the supernodes in the network.
The Supernodes try to make both ends to negotiate directly the connection, but if it's not possible due to firewalls, NAT, etc they relay the traffic on behalf of two or more clients.