Gampong Paya bili dahulunya adalah daerah yang banyal rawa rawa (Paya), menurut cerita gampong ini sudah ada sejak tahun 1980-an, pada awalnya ketika beberapa orang datang membuka lahan ke paya bili, mereka menemukan bahwa daerah tersebut banyak sekalai rawa-rawa (Paya) yang keadaannya sangat berlumpur dan dalam sehingga menurut sejarah mereka membuat jembatan serba bisa dari pohon pinang yang yang hanya berukuran kecil supaya bisa melewati daerahdaerah rawa tersebut. singkat cerita gampong ini terjadi dengan dibuka lahan dari rawa-rawa atau orang dahulu meyebutnya dengan cah paya. pada saat membuka lahan mereka menemukan pohoh Bili yang berukuran besar, biasanya pohon bili ini berukuran kecil hanya sebesar jempol kaki atau paling besar seukuran gagang parang atau pun pisau, namun yang mereka temukan ini berukuran sangat besar diantara yang lainnya, menurut cerita dikatakannya bahwa pohon tersebut hampir sebesar pohon bambu, maka ketika lahan sudah ada akhir nya pada saat sedang beristirahat mereka berfikir danberembuk untuk memberikan nama desa tersebut dari hasil kesepakan bersama maka muncullah ide untuk menamakan desa ini dengan nama PAYA BILI Asal kata paya (Rawa) dari rawa yang mereka babat bersama dan Bili dari pohon bili besar yang mereka temukan. gampong paya bili sudah diakui sebagai sebuah gampong sejak zaman pemerintahan belanda, sejak zaman penjajahan belanda dan zaman penjajahan jepang, gampong paya bili sudah berdiri sendiri sebagai sebuah gampong yang berdaulat, sehingga pada masa setelah kemerdekaan gampong paya bili pun sah sebagai salah satu gampong yang ada dikecamatan muara dua. tidak ada sejarah pasti yang tercantum dan akurat terhadap sejarah desa. hanya sejarah turun temurun yang menjadikan bukti sejarah hingga saat ini. namun menurut cerita kalau berdasarkan pengkajian dan sejarah dari tokoh masyarakat yang sudah tua, bahwa mereka pernah merasakan zaman pendudukan belanda dan juga menyaksikan bagaimana belanda diusir oleh jepang kemudian dijajah oleh belanda, ini menunjukkan bahwa gampong ini setidaknya sudah ada sejak tahun 1980-an.