This paper presents a detailed analysis of the influence of sulfur formation on performance and efficiency of Solid Oxide Fuel Cells (SOFC) operating on methane containing fuels. Our previously developed multi-step reaction mechanism of sulfur formation and oxidation is coupled with a complex heterogeneous mechanism of methane reforming, channel gas-flow, porous-media transport and elementary kinetic charge transfer and is used to describe sulfur-induced degradation and performance drops of Ni/YSZ anodes. Experimental literature data is used to validate the model and to interpret important aspects of cell performance degradation. Comparisons of the model predictions to the experiments illustrate that the developed model, without any modifications, reproduces the observed voltage decrease well and is able to capture the changes in fuel conversion and selectivity for different gas mixtures. It is shown that atomically adsorbed sulfur significantly influences heterogeneous reforming chemistry, causing substantial voltage degradation. At constant current densities, cell voltage decreases in a non-linear way with faster recovery than in H2/H2O mixture.