While SOFCs are the most flexible fuel cells with respect to fuel selection, fuel impurities in practical SOFC fuels can cause degradation of electrodes and thus electrochemical performance. The understanding of fuel impurity poisoning and the increase in tolerance are therefore of technological relevance for SOFC commercialization. Along with thermochemical calculations on the stability of typical fuel impurities under SOFC operational conditions, fuel impurity poisoning of SOFCs is analyzed by using various impurity-containing fuel gases with respect to operational temperature, type and concentration of impurities, fuel composition, and steam-to-carbon ratio. We have revealed that poisoning depends on operational conditions and types of fuels and impurities. The poisoning effect becomes significant for internal-reforming SOFCs operated with humidified methane-based fuels. Poisoning mechanisms are discussed, based on cell voltage and durability data.