Methods and apparatus that allow clients to connect resource instances to virtual networks in provider network environments via private IP. Via private IP linking methods and apparatus, a client of a provider network can establish private IP communications between the client's resource instances on the provider network and the client's resource instances provisioned in the client's virtual network via links from the private IP address space of the virtual network to the private IP address space of the provider network. The provider network client resource instances remain part of the client's provider network implementation and may thus also communicate with other resource instances on the provider network and/or with entities on external networks via public IP while communicating with the virtual network resource instances via private IP.