Xylella fastidiosa is responsible for a wide range of economically important plant diseases. We report here the crystal structure and kinetic data of Xylellain, the first cysteine protease characterized from the genome of the pathogenic X. fastidiosa strain 9a5c. Xylellain has a papain-family fold, and part of the N-terminal sequence blocks the enzyme active site, thereby mediating protein activity. One novel feature identified in the structure is the presence of a ribonucleotide bound outside the active site. We show that this ribonucleotide plays an important regulatory role in Xylellain enzyme kinetics, possibly functioning as a physiological mediator.