The mechanisms governing the sulfur poisoning of the triple phase boundary (TPB) of Ni-XSZ (X2O3 stabilized zirconia) anodes have been investigated using density functional theory. The calculated sulfur adsorption energies reveal a clear correlation between the size of the cation dopant X(3+) and the sulfur tolerance of the Ni-XSZ anode; the smaller the ionic radius, the higher the sulfur tolerance. The mechanistic study shows that the size of X(3+) strongly influences XSZ's surface energy, which in turn determines the adhesion of Ni to XSZ. The Ni-XSZ interaction has a direct impact on the Ni-S interaction and on the relative stability of reconstructed and pristine Ni(100) facets at the TPB. Together, these two effects control the sulfur adsorption on the Ni atoms at the TPB. The established relationships explain experimentally observed dopant-dependent anode performances and provide a blueprint for the future search for and preparation of highly sulfur tolerant anodes.