There is increasing interest in the role of legitimacy in post-war societies as an indicator of social and political stability. In this chapter we propose an analytical framework that examines post-war peacebuilding processes by focusing on two central concepts: legitimacy and actors. We understand peacebuilding as rooted in the relationship between politics, namely the state in particular, and the wider society. Peacebuilding is the process wherein the structural-normative setup of the post-war state vis-à-vis society is renegotiated through various interactions between domestic state and non-state actors with, or without, the involvement of international or other external actors. The degrees to which this domestic relationship will be sustainable and peaceful is largely contingent on whether society finds it legitimate, or not. This understanding of legitimacy is important because it recognizes the importance of relational agency, which neither rejects the role and existence of the state, nor understates the agency of society in the process of rebuilding countries after internal armed conflict. Applying the framework on empirical insights from Afghanistan and Nepal, this chapter highlights the importance of relational agency and the perceived legitimacy of the domestic state-society relationship.