Cerkev se prvič omenja leta 1526, drugič jo 160 let kasneje omenja Janez V. Valvasor v Slavi vojvodine Kranjske. Stara cerkev je bila leta 1859 porušena. Takrat so grič znižali za 4 m, odstranili obzidje in dobili so več prostora. Gradil jo je župnik Blaž Artel.
Blaž Artel je na Sela pri Kamniku prišel leta 1856 kot četrti duhovni upravitelj. Kmalu po prihodu je začel razmišljati o zidavi nove cerkve sv. Neže, saj je bila stara gotska cerkev, ki je sicer doživela več prezidav, premajhna. Leta 1858 so na Selih in okolici začeli s pripravo gradbenega materiala za gradnjo cerkve. Po tihi nedelji (druga nedelja pred veliko nočjo) leta 1859 so začeli s podiranjem stare cerkve. Da bi povečali površino, so cerkveni grič znižali za 4 m. Nova cerkev je bila leta 1859 že pod streho, novembra 1860 so jo blagoslovili, dne 4. 8. 1861 pa jo je posvetil ljubljanski škof dr. Jernej Vidmar. Gradnjo cerkve so spremljale velike denarne težave. Za pomoč pri gradnji je Blaž Artel zaprosil tudi upokojenega cesarja Ferdinanda, ki je februarja 1861 prispeval 400 goldinarjev za notranjo opremo cerkve.