Systems and methods are provided for enforcing symmetric flows of cross-region network traffic through firewalls in multi-region network environments. Enforcement may be configured automatically by analyzing network policy data to identify cross-region traffic that is to be firewalled, and configuring gateway nodes in the various regions to implement symmetric bidirectional flows through any firewalls in the communication path. Beneficially, by enforcing symmetric bi-directional flows of traffic through any firewalls in a communication path, the firewalls may maintain the state of a given communication session even when the communication session is between endpoints in different regions that have different architectures.