Fast and accurate parameter extraction of fuel cells is crucial to the control and performance analysis of fuel cell power systems. Unfortunately, due to the multivariable and nonlinear features of fuel cell models, it is a difficult task to identify the parameters of the models. In this paper, we propose a decomposition technique, where the unknown parameters are divided into two groups: nonlinear and linear. The optimization techniques only need to optimize the nonlinear parameters, and then the linear parameters are determined based on the nonlinear ones. With the help of the decomposition technique, a generalized framework by using the nature-inspired optimization method is proposed to try to fast and accurately extract the parameters for different types of fuel cells. To test the performances of our approach, two widely used types of fuel cells are studied, i.e., proton exchange membrane fuel cell and solid oxide fuel cell. Extensive simulation tests with thirty-two instances are carried out for comparing our approach with existing approaches. The comparison demonstrates the efficiency of the decomposition technique. Moreover, the results show that our approach can not only significantly reduce the computational resources, but also yields high quality solutions.