Stateful firewalls are security solutions widely deployed in the Internet. These devices filter network traffic and keep track of the state of connections in order to make the deployment of several attacks, such as TCP resets, difficult. However, firewalls are critical equipments in the network schema since they introduce a single point of failure. Therefore, a failure may isolate networks, users and interrupt established connections. Current fault tolerant solutions mask failures by means of replication techniques based on physical redundancy and state propagation. However, these solutions do not suit well for stateful firewall scenarios since they reduce bandwidth throughput roughly, they require costful extra hardware or are stuck to wasteful and inflexible single primary-backup settings. In this work we detail FT-FW (Fault Tolerant FireWall), a software-based transparent connection failover mechanism for stateful firewalls. Our solution has a negligible impact in terms of performance, as well as the fact that quick recovery from failures and fast responses to clients are guaranteed. The architecture is suitable for low cost off-the-shelf systems and no extra hardware is required.