This paper explores rebel legitimacy building by investigating rebel network formation during civil wars. Through a longitudinal study of the Moro Islamic Liberation Front, it examines various mechanisms through which a non-state armed group (NSAG) embellishes and enhances its legitimacy among domestic and international support networks. The research also theorizes the complex interaction between domestic and international legitimacy, when and why NSAGs prioritizes politically prestigious network over initial resource-based one, and the impact of the shift on rebel behavior. The causal process explores how rebels’ legitimacy consideration affects their lobbying and coalition-building efforts.