Masjid Agung Nurul Huda merupakan masjid kuno yang telah ada pada masa awal pemerintahan Kesultanan Sumbawa. Belum ditemukan data pasti kapan masjid berdiri, sekitar tahun 1648 atau tahun 1881 (1299 H). Namun, bila mengacu pada mimbarnya yang bertarikh 1299 H/1878 M, kini tersimpan di Museum Daerah Sumbawa. Maka dipastikan masjid ini sudah ada jauh sebelum tahun 1881. Sejak awal Kesultanan Sumbawa telah memiliki masjid dengan bentuk bangunan sederhana. Seiring dengan pesatnya perkembangan Islam pada zaman dahulu, Kesultanan Sumbawa memutuskan untuk membangun masjid baru. Adapun bangunan masjid yang berdiri sekarang ini merupakan masjid hasil pemugaran. Nama Masjid Agung Nurul Huda disematkan setelah masjid dirobohkan dan dibangun kembali pada masa pemerintahan Bupati Sumbawa Yakub Koeswara (1989-1999). Keberadaan masjid menjadi bukti sejarah panjang proses penyebaran Islam di Sumbawa, Nusa Tenggara Barat. Selain itu, letak masjid juga bersebelahan dengan Istana Dalam Loka yang mengisyaratkan betapa kuatnya pengaruh Islam dalam pemerintahan Kesultanan Sumbawa.