South Korea and Taiwan are former Japanese colonies that have undergone similar processes of state-building since WWII. But they have chosen different rhetorical frameworks in their maritime disputes with Japan. In South Korea, negotiating with Japan can be viewed as threatening the country’s independence and pride, whereas in the Taiwanese government, cooperation with Japan is considered mutually beneficial. Why have these two countries taken such divergent stances toward Japan? This article examines the territorial disputes between South Korea and Japan over Dokdo, and between Taiwan and Japan over the Senkaku Islands. It sets forth a rhetorical framework of comparison, and it proposes a constructivist perspective in understanding South Korea’s and Taiwan’s legitimation strategies toward Japan from the late 1990s to 2018. This comparative study suggests that the differences between their legitimation strategies can be traced to their different colonial experiences with Japan.