This paper describes context-dependent substroke hidden Markov models (HMMs) for on-line handwritten recognition of cursive Kanji and Hiragana characters. As there are more than 6,000 distinctive characters including Kanji and Hiragana in Japanese, modeling each character by an HMM leads to an infeasible character-recognition system requiring huge amount of memory and enormous computation time. 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 drawback of this approach is that the recognition accuracy deteriorates in case of scribbled characters, and characters where the shape of the substrokes varies a lot. In this paper, we show that the context-dependent substroke modeling which depends on how the substroke connects to the adjacent sub-strokes is e....ective to achieve robust recognition of low quality characters. The Successive State Splitting (SSS) 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 handwritings and from 90% to 98% for Hiragana handwritings.