Proteolysis of eukaryotic histone tails has emerged as an important factor in the modulation of cell-cycle progression and cellular differentiation. The recruitment of lysosomal cathepsin L to the nucleus where it mediates proteolysis of the mouse histone H3 tail has been described recently. Here, we report the three-dimensional crystal structures of a mature, inactive mutant of human cathepsin L alone and in complex with a peptide derived from histone H3. Canonical substrate-cathepsin L interactions are observed in the complex between the protease and the histone H3 peptide. Systematic analysis of the impact of posttranslational modifications at histone H3 on substrate selectivity suggests cathepsin L to be highly accommodating of all modified peptides. This is the first report of cathepsin L-histone H3 interaction and the first structural description of cathepsin L in complex with a substrate.