When writing an object's name, humans mentally construct its spelling. This capacity critically depends on use of the dual-structured linguistic system, in which meaningful words are represented by combinations of meaningless letters. Here we search for the evolutionary origin of this capacity in primates by designing dual-structured bigram symbol systems where different combinations of meaningless elements represent different objects. Initially, we trained Japanese macaques (Macaca fuscata) in an object-bigram symbolization task and in a visually-guided bigram construction task. Subsequently, we conducted a probe test using a symbolic bigram construction task. From the initial trial of the probe test, the Japanese macaques could sequentially choose the two elements of a bigram that was not actually seen but signified by a visually presented object. Moreover, the animals' spontaneous choice order bias, developed through the visually-guided bigram construction learning, was immediately generalized to the symbolic bigram construction test. Learning of dual-structured symbols by the macaques possibly indicates pre-linguistic adaptations for the ability of mentally constructing symbols in the common ancestors of humans and Old World monkeys.