This disclosure describes techniques for implementing network address translation as a distributed service over the nodes of a logical network fabric, such as a software-defined network fabric. A method includes registering, by an edge node of a network, an IP address of a client device. The method further includes forwarding, by the edge node, the registered IP address to a control plane of the network. The method further includes checking, by the control plane, a network address translation policy. The method further includes recording, by the control plane, translations between the registered IP address and an allocated IP address in a translation table, each of the translations being related to the edge node. The method further includes returning, by the control plane, the translations between the registered IP address and the allocated IP address to the edge node.