This paper describes a new handwritten address recognition method which can correct the errors occurring in line extraction, character segmentation, and character recognition as a possible means of avoiding the error accumulation which occurs during the recognition sequence in conventional methods. We formulated the address recognition method as a minimum cost search problem. We defined the character recognition cost which estimates the reliability of the character recognition result, the arrangement cost which estimates the plausibility of the character string's spatial arrangement, and the word knowledge cost which estimates the plausibility of the linguistic conditions. By using a combination of these costs, the proposed method can recognize an address which has not been extracted as a single line from input images by a conventional method. The efficiency of the proposed method is evaluated through an experiment using 600 Japanese mail images. An address recognition rate of 79.38% was obtained.