Even though some measures to reduce the incidence rate of child marriage have being undertaken for years, the implementation of the marriage act, Undang-undang No.16/2019, has been strengthening the implementation of Program Pendewasaan Usia Perkawinan (PUP), a national program to reduce the incidence rate of child marriage in Indonesia. Under these circumstances, communication holds an essential role in that program, mainly to reach behavioral and social changes among community as the main target of the program. A number of previous research still focused on the role of communicators and the communication effectiveness of the program. Through narrative paradigm framework, the present study is conducted to explore story-telling strategies performed by extension agents in Kabupaten Pasuruan, a distric where the incidence rate of child marriage is relatively high. Data gathered through FGDs and indepth interviews which involved extension agents of Program PUP in Kabupaten Pasuruan, local authority that concerns in family welfare and women empowerment, and Muslimat NU – those directly involved in the communication and education process towards PUP Program. Through interactive analysis presented by Miles, Huberman & Saldana (2014), this study revealed that within their strory-telling strategies, the extension agents as a story-teller tends to performed themselves in a more symmetrical relationship with their audiences. In order to involve their audiences to their stories, the extension agents employed Islamic based stories. From the structural narration, it is clear that they use humor and mitos to convince their audiences to avoid child marriage. The stories used also performed both structural and characterological coherence. However, in some stories, there are still lack of material coherence. Meskipun penanganan masalah pernikahan usia anak telah sejak lama dilakukan, berlakunya Undang-Undang Nomor 16 Tahun 2019 tentang perkawinan semakin memperkuat pelaksanaan Program Pendewasaan Usia Perkawinan (PUP) sebagai langkah konkret penanganan tingginya pernikahan usia anak di Indonesia. Komunikasi pada akhirnya turut memegang peranan kunci dalam proses pelaksanaan program khususnya untuk mencapai perubahan dalam level masyarakat sasaran. Berkaitan dengan PUP, berbagai riset terdahulu masih banyak berfokus pada peran komunikator serta efektivitas proses pengomunikasian program. Melalui kerangka narrative paradigm, penelitian ini hadir dengan tujuan mengeksplorasi strategi komunikasi berbasis storry-telling yang telah dilakukan oleh para penyuluh lapangan di wilayah Kabupaten Pasuruan, wilayah dengan jumlah pernikahan usia anak yang cukup tinggi. Teknik pengumpulan data dilakukan melalui FGD dan wawancara dengan melibatkan para penyuluh lapangan Program PUP di Kabupaten Pasuruan, dinas terkait, serta Muslimat NU yang terlibat langsung dalam proses edukasi terkait PUP. Melalui analisis interaktif Miles et al (Miles, M.B; Hubberman, A.M,; Saldana, 2014), disimpulkan bahwa melalui strategi story-telling yang digunakan, para penyuluh selaku pencerita berusaha memposisikan dirinya dengan membawakan cerita yang didasarkan pada penggunaan kisah-kisah dalam sejarah Islam untuk melibatkan target audiens di dalam cerita mereka. Dari struktur narasi yang digunakan, secara umum cerita yang disampaikan melibatkan humor dan mitos dan telah dapat memenuhi koherensi struktural dan karakterologis. Akan tetapi, terdapat beberapa cerita yang belum menunjukkan koherensi material.