Masjid Gadang Balai Nan Duo sekarang bernama Masjid gadang Koto Nan IV yang terletak sekitar 200 m dari Rumah Gadang Balai Nan Duo. Masjid ini merupakan masjid tertua yang ada di Kota Payakumbuh. Masjid didirikan setelah dibangunnya Rumah Gadang Sutan Chedoh (sekarang bernama Rumah Gadang Balai Nan Duo) yang dahulunya disebut juga Istana Regent. Kalau cerita itu benar, maka diperkirakan usia masjid sudah hampir mencapai 200 tahun.
Hal ini berdasarkan pada buku autobiografi HC Israr yang mengatakan bahwa Payakumbuh ditaklukan oleh kolonial pada tahun 1823. Kemudian Belanda mengangkat Sutan Chedoh sebagai Regent di sana, sebagai penghargaan atas jasa-jasanya. Setelah diangkat menjadi Regent Sutan Chedoh kemudian mendirikan Rumah Gadang Balai Nan Duo (Istana Regent) dan Masjid Gadang Balai Nan Duo sebagai rumah dan tempat ibadah baginya. Dalam perjalanannya bangunan masjid sudah banyak yang diperbaiki/direhab oleh masyarakat (pengurus masjid) seperti atap, loteng, lantai dan dinding.
Masjid Gadang Balai Nan Duo merupakan suatu kompleks yang terdiri dari beberapa bangunan. Bangunan utama adalah masjid yang berada dibagian tengah, kemudian bangunan tambahan berupa perpustakaan, TPA (sisi barat), dan wc dan rumah garin di sisi selatan (depan pintu masuk masjid). Pada bagian utara masjid (dekat mihrab) terdapat juga sebuah bangunan dari bahan bata berspesi berbentuk kerucut (belum diketahui tokohnya) dan tempat parkir.
Bangunan Masjid Balai Nan Duo mempunyai atap tumpang tiga dari bahan seng dengan kemuncaknya berupa mustoko yang runcing di atas. Antara atap yang atas dengan bawahnya diberi dinding papan yang berhiaskan ukiran matahari, sedangkan antara atap tengah dan bawah juga diberi pembatas dinding papan dengan ukiran yang hampir sama.
Bangunan masjid berbentuk bujur sangkar dengan ukuran 17,6 m x 17,9 m yang berada dalam areal seluas 45,5 m x 43 m x 50 m. Secara umum bangunan masjid berbahan kayu (dinding, loteng dan lantai). Tiang penyangga masjid keseluruhan berjumlah 21 buah yang terdapat ditengah-tengah ruangan masjid. Tiang-tiang ini disusun/berjejer dalam jumlah 5,4, dan 3. Tiang penyangga terbuat dari kayu berbentuk bulat. Pada tiang bagian atas terdapat ornamen berbentuk mahkota. Dari 21 buah tiang, terdapat empat buah tiang yang menggantung, dalam artian puncaknya tidak menyatu dengan langit-langit. Sedangkan mihrab terletak di sisi utara dengan ukuran 6,5 m x 1,7 m yang dilengkapi dengan mimbar.
Pada sisi selatan masjid (pintu masuk) terdapat anak tangga yang terbuat dari semen dilapisi keramik warna putih dengan ukuran luas 7 m x 4 m. Tangga masuk ini berbentuk melingkar.