Fault tolerance is essential to the development of reliable mobile agent system in order to guarantee continuous execution of mobile agents. For this purpose, some previous works have proposed fault tolerant protocols for mobile agent execution based on stage construction. However, when previous protocols are applied to a multi-region mobile agent computing environment, the overhead of stage works such as monitoring, election, voting and agreement is increased. In this paper, we propose a region-based stage construction (RBSC) protocol for fault tolerant execution of mobile agents in a multi-region mobile agent computing environment. The RBSC protocol uses new concepts of quasi-participant and substage in order to put together some places located in different regions within a stage in the same region. Therefore, the RBSC protocol decreases the overhead of stage works. Consequently, the RBSC protocol decreases the total execution time of mobile agents.