This essay analyzes challenges and opportunities of the newly independent East Timor, a territory in the process of nation-building and conflict transformation. The analysis focuses on two levels of tranformative capacity building—the formal government institutions and the social relationships outside the government. At the institutional level, East Timorese military personnel, political parties, and elected representatives possess the potential to develop dynamic relations conducive to the sustainable capacity of domestic conflict transformation. On the social relationship side, three sets of paradoxical orientations involved in conflict transformation—personal versus contextual change, justice versus mercy, and empowerment versus interdependence—are explored in the context of East Timor’s nation-building. The author argues within both levels of conflict transformation, East Timor needs to establish and strengthen sustainable mechanisms of communication with Jakarta in order to deter potential threats that may originate from Indonesia’s domestic politics, as well as from the broader international context. The analysis concludes with a brief discussion on the inevitability of time pressure on East Timor’s nation-building process, and how the post-Cold War regional security climate is likely to present unique challenges for its way forward.