Lysine propionylation is a recently identified post-translational modification that has been observed in proteins such as p53 and histones and is thought to play a role similar to acetylation in modulating protein activity. Members of the sirtuin family of deacetylases have been shown to have depropionylation activity, although the way in which the sirtuin catalytic site accommodates the bulkier propionyl group is not clear. We have determined the 1.8 Å structure of a Thermotoga maritima sirtuin, Sir2Tm, bound to a propionylated peptide derived from p53. A comparison with the structure of Sir2Tm bound to an acetylated peptide shows that hydrophobic residues in the active site shift to accommodate the bulkier propionyl group. Isothermal titration calorimetry data show that Sir2Tm binds propionylated substrates more tightly than acetylated substrates, but kinetic assays reveal that the catalytic rate of Sir2Tm deacylation of propionyl-lysine is slightly reduced to acetyl-lysine. These results serve to broaden our understanding of the newly identified propionyl-lysine modification and the ability of sirtuins to depropionylate, as well as deacetylate, substrates.