Speech labeling is an indispensable task for construction of speech data bases. Currently, speech labeling is done manually by experts. Thus it takes too much time and labor to label large amount of speech data. In order to decrease such labor, it is necessary to construct an automatic labeling system. The authors have been developing a speech labeling system based on a generate-and-test architecture with segmentation knowledge. Performance evaluation shows that for closed data, 99.1% segments are identified within 30ms of the locations determined by a human expert and 95.5% segments are also identified correctly for open data with rejection rates of 6.7% and 8.9%, respectively. This paper describes the system organization and the results of performance evaluation.