This work explores different types of FPGA structures for evolving fault tolerant hardware. A three-tier model for providing fault tolerance to the digital circuits evolved on FPGAs is proposed. This model combines the process level redundancy provided by the GA based evolution techniques and the structural level redundancy supported by the FPGA architectures. Simulation results using the ISCAS?89 benchmark circuits have been carried out to study the effect of granularity on the time taken for the evolution process, the dimensionality of the evolution and the number of solutions that need to be evolved for fault coverage. The effect of using a divide and conquer approach to reduce the time taken for evolution has been studied proving that this is a feasible approach even for complex circuits.