Systems and methods are provided to perform operations on a packet of network traffic based on a routing rule of the packet. A stateful network routing service may include multiple network gateways for receiving packets of network traffic. The stateful network routing service may receive a packet and obtain or generate a routing rule based on the source and destination of the packet based on receiving the packet via a client-facing network gateway. The stateful network routing service may transmit the packet to a network appliance based on the routing rule. The stateful network routing service may further receive a packet via an appliance-facing network gateway. Based on receiving the packet via the appliance-facing network gateway, the stateful network routing service may decapsulate the packet and transmit the packet to a network destination. The stateful network routing service may further validate the packet.