Existing scholarship attributes the onset of state-to-state rapprochement to unilateral con- cessions made by one rival to another. However, it is unclear why the receiving side will reciprocate, instead of exploit, the act of accommodation—a quintessential commitment problem that plagues conflict resolution. This paper complements the extant knowledge and sheds new light on the requirements for, and mechanisms leading to, successful interstate reconciliation. The research here suggests when normal communication is hindered by rivalry, the existence of parallel self-interest between rivals and the successful mutual recognition of such interests through behind-the-scenes diplomacy are key to realize state-to-state reconciliation. A comparative historical analysis between failed Cross-Taiwan Strait reconciliatory efforts in 2000 and successful ones in 2008 shows that reciprocity did not stem from unilateral concessions. Instead, the Sino-Taiwanese rapprochement that began in 2008 was preceded by a laborious process of behind-the-scenes diplomacy, where consistent signaling changed the Chinese Communist Party’s and the Kuomintang’s perceived intention and interests of the other. The consistent signaling helped the two parties ascertain their parallel interests, which made a tacit understanding of mutual restraint self-enforcing and alleviate the commitment problem.