Sejarah Iceland mencatatkan ketibaan para duta daripaa sultan Muslim Tunisia di Norway pada 1260-an, setelah raja Håkon Håkonsson mengirimkan duta kepada sultan dengan hadiah-hadiah kaya. Adalah masuk akal untuk menganggap bahawa orang Muslim telah juga melawat Norway lebih awal daripada ini. Tetapi tiada penduduk Muslim yang nyata di Norway sehingga separuh abad ke-20 yang kedua. Imigrasi dari negara-negara Muslim ke Norway agak lewat, dibandingkan dengan negara-negara Eropah lainnya, dan tidak maju sehingga lewat 1960-an. Pada 1975, immigrasi sumber manusia ke Norway telah dihentikan, tetapi peraturan untuk penyatuan keluarga dibiarkan longgar untuk beberapa tahun lagi.

Bilangan Muslim di Norway didaftarkan pertama kali dalam statistik rasmi pada 1980, ketika itu ia diberikan sebagai 1006. Statistik ini berdasarkan keahlian dalam jemaah berdaftar, dan ia kemungkinannya lebih kecil daripada jumlah sebenar kerana beberapa Muslim sahaja menjadi ahli sesebuah masjid. Sejarawan agama Kari Vogt mentafsirkan bahawa 10 % Muslim Norway menjadi ahli sebuah masjid pada 1980, sebuah perkadaran yang telah bertambah kepada 70 % pada 1998. Menjadi ahli sebuah masjid ialah konsep asing untuk ramai pendatang dari negara-negara Muslim. Di Norway, adalah harus masjid-masjid mendaftarkan ahli-ahli mereka, kerana kerajaan meluluskan peruntukan untuk jemaah keagamaan selain gereja negara berdasarkan pada bilangan ahli-ahli berdaftar. Bilangan ini berdaftar bertambah kepada 80 838 pada 2004, tetapi telah menurun kepada 72 023 pada 2006. Sebahagian sebab untuk penurunan ini kemungkinannya metodologi baru pada pengumpulan statistik .

Pada akhir 1990-an, Islam melangkaui Gereja Roman Katolik dan Pentecostalisme untuk menjadi minoriti terbesar di Norway, sekiranya Islam dilihat sebagai satu jemaah bersatu. Pada 2004, orang Muslim merupakan ahli kepada 92 jemaah berlainan. 40 daripada ini bertempat di Oslo atau daerah Akershus.