Sulfur poisoning in Ni-based catalysts, one of the most critical problems in solid oxide fuel cells (SOFC), has been extensively examined at the atomic level by density functional theory (DFT). In the reversible poisoning process with atomic sulfur adsorption, the poisoning mechanism has been studied by elucidating the potential energy surface (PES) of the interfacial reactions between the sulfur contaminants (such as H2S) and Ni surfaces. The computed low reaction barriers (< 0.45 eV) and high exothermicities (< -2.51 eV) of the processes indicate that H2S can easily react and poison Ni surfaces. In the irreversible poisoning process forming nickel sulfide, the intrinsic properties of the nickel sulfide have been studied by examining its vibrational frequencies and density of states (DOS). The frequency analysis is vital to the identification with in-situ vibrational spectroscopy during the poisoning processes. The DOS analysis will be applied to understand the degradation behaviors (decrease of catalytic activity) in the sulfur-contaminated Ni catalysts. Furthermore, with thermodynamic corrections, a new computed Ni-S phase diagram precisely predicts the boundaries of the reversible and irreversible poisoning behaviors; the result agrees well with experimental observations.