A multi-tenant cloud-based firewall method from a client, performed by a cloud node, includes receiving a packet from the client, wherein the client is located externally from the cloud node; checking if a firewall session exists for the packet, and if so, processing the packet on a fast path where a lookup is performed to find the firewall session; if no firewall session exists, creating the firewall session; and processing the packet according to the firewall session and one or more rules. The cloud node can perform the method without a corresponding appliance or hardware on premises, at a location associated with the client, for providing a firewall.