Describes context-dependent substroke hidden Markov models (HMMs)for on-line handwritten recognition of cursive Kanji and Hiragana characters. In order to tackle this problem, we have proposed the substroke HMM approach where a modeling unit "substroke" that is much smaller than a whole character is employed and each character is modeled as a concatenation of only 25 kinds of substroke HMMs. One of the drawbacks of this approach is that the recognition accuracy deteriorates in the case of scribbled characters, and characters where the shape of the substrokes varies a lot. We show that the context-dependent substroke modeling which depends on how the substroke connects to the adjacent substrokes is effective for achieving robust recognition of low quality characters, The successive state splitting algorithm which was mainly developed for speech recognition is employed to construct the context dependent substroke HMMs. Experimental results show that the correct recognition rate improved from 88% to 92% for cursive Kanji handwriting and from 90% to 98% for Hiragana handwriting.