The Cellular IP protocol utilizes a gateway architecture to achieve better handoff performance. However, the gateway may become a single point of failure in the network. If the gateway fails, the domain network serviced by the gateway will be disconnected. This issue is not addressed in the original Cellular IP design. This paper introduces the concept of multiple gateways for tolerating failures on the gateways, the base stations, and the communication links. The gateways coordinate with each other for serving the mobile nodes. When failures occur, an available gateway will take over the operations. The fault-tolerant Cellular IP protocol was evaluated using the network simulator ns-2. The results show that the protocol not only improved the disconnection time but had little impact on the transmission performance.