A method of providing efficient access to cloud services in a network that includes a several tenant logical networks and a set of service logical networks. The method receives, from a particular tenant VM, a first packet that specifies a destination address associated with a service VM of a service logical network. The method, based on the destination address of the first packet, replaces the source network address and source port number of the first packet with one of a set of network address and port number pairs allocated for accessing service VMs. The method receives from the particular VM a second packet that specifies a destination address outside the tenant logical network but not associated with any service VM. The method, without modifying the source address and port number of the second packet, forwards the second packet to a network element outside the host for network NAT processing.