Listina iz leta 1091 omenja, da je grof Engelbert Spanheimski daroval samostanu v Št. Pavlu na Koroškem posestvo “Heremum Radinlac didctam” to je današnjo Puščavo in Lovrenc. Isti grof je v 11. st. pri kapeli sv. Lovrenca ustanovil majhen samostan. Sčasoma je nastalo več kapelic, med njimi tudi kapelica sv. Štefana, kjer stoji sedaj župnijska cerkev Device Marije v Puščavi. Skraja so za božjo pot skrbeli Benediktinci. Ko pa so leta 1782 morali kraj zapustiti, je 1786 postala samostojna kuracija in je prišla pod oskrbo škofijskih duhovnikov iz Lovrenca. Leta 1784 je bila kuracija Device Marije v Puščavi povzdignjena v župnijo. 

Na spominski plošči, vzidani na zunanji strani cerkve, se da razbrati, da je v letih 1622 – 1627, dal zgraditi to cerkev Šentpavelski opat Hieronim Markstaler. Domnevajo, da je stala ta cerkev v smeri vzhod (glavni oltar) zahod. Predelal in povečal pa jo jo l. 1672 njegov naslednik Filip Rotenhaustler v smeri jug (glavni oltar) sever.