This paper presents a new model formulation based on fractional order transfer functions (FOTF) for the modeling frequency response data (impedance) of hydrogen polymer electrolyte membrane fuel cells. Due to non-convexity of the minimization problem associated with the identification of the model parameters and the possible outliers contaminating the experimental data-set, a novel optimization strategy is proposed to reduce the risk of poor parameter estimation. This stochastic strategy is a modified random consensus sampling algorithm (RANSAC) which uses the Levenberg-Marquardt (LM) method to solve the inner optimization problem. The new model formulation and the optimization strategy were tested using an experimental data-set composed of three frequency response curves recorded from a PEMFC operating at different conditions. The results show that the proposed model formulation can be adjusted with a high accuracy to the experimental data, thus allowing the estimation of good quality parameters from experimental impedance data. © 2011 Elsevier B.V.