Split intein-mediated protein trans-splicing (PTS) is widely applied in chemical biology and biotechnology to carry out traceless and specific protein ligation. However, the external residues immediately flanking the intein (exteins) can reduce the splicing rate, thereby limiting certain applications of PTS. Splicing by a recently developed intein with atypical split architecture ("Cat") exhibits a stark dependence on the sequence of its N-terminal extein residues. Here, we further developed Cat using error-prone polymerase chain reaction (PCR) and a cell-based selection assay to produce Cat*, which exhibits greatly enhanced PTS activity in the presence of unfavorable N-extein residues. We then applied solution nuclear magnetic resonance spectroscopy and molecular dynamics simulations to explore how the dynamics of a conserved B-block histidine residue (His) contribute to this extein dependence. The enhanced extein tolerance of Cat* reported here should expand the applicability of atypically split inteins, and the mechanism highlights common principles that contribute to extein dependence.