The enactment of Law No. 23 of 2014 concerning Local Government in Indonesia has paved the way for increased international engagement by local authorities, a practice known as paradiplomacy. In this context, Nusa Tenggara Barat (NTB) has sought to expand its international cooperation, notably with Bukhara Province, focusing on developing the halal tourism sector. This study critically examines the process and challenges of institutionalizing paradiplomacy between NTB and Bukhara, with a particular focus on halal tourism development. However, the institutionalization of this international cooperation has encountered significant obstacles. Utilizing a qualitative research approach, this investigation analyzed a variety of primary and secondary sources to uncover the underlying factors impeding the process. The study identified several key barriers to the institutionalization of NTB-Bukhara paradiplomacy, including shifts in leadership and policy priorities within NTB's government, delays in formalizing cooperation agreements, a lack of expertise in international relations among local government officials, restrictive central government regulations, and cultural and conceptual discrepancies in the understanding of halal tourism between the two regions. Addressing these challenges requires a multifaceted approach, involving not only policy reform and capacity building at the local government level but also a deeper cultural and conceptual alignment between cooperating entities.