A flow policy service that allows clients to define policies for packet flows to, from, and within their virtual networks on a provider network. Via the service, a client may define rules that specify appliances that inbound, outbound, and/or internal virtual network traffic should flow through. The rules may, for example, be attached to the virtual network, to subnets within the virtual network, and/or to resource instances within the virtual network. The rules may be specified in a descriptive, domain-specific language. The service determines how and where on the provider network to implement the rules in order to apply the specified policy. Thus, the actual implementation of the policy may be hidden from the client. The service may generate flow reports that may be used to confirm that traffic to, from, or within a virtual network is flowing through the correct network appliances according to the policy.