Prvotna cerkvica je bila postavljena v 12. stoletju. V starih listinah se prvič omenja leta 1374 kot kapelaVneser Lieben Frauen auf dem Stain. Kot cerkev pa je prvič omenjena leta 1383 v listini, iz katere je razvidno, da so grofHerman II. in vuzeniški župnikUlrik ter trškisodnikNikolaj Schaissbacher ustanovili nadarbino za kaplana, ki bo vsak dan pred sončnim vzhodom maševal v tej cerkvi.
Leta 1500 so cerkev povečali, 1666 postavili sedanji glavni oltar in prizidali zunanjo kapelo. Cesar Jožef II. je hotel 1783 cerkev opustiti, farani pa so se zavezali, da jo bodo sami vzdrževali in jo tako tudi obdržali. A.M. Slomšek, ki je v Vuzenici služboval od 1838 je leta 1842 vodil gradnjo prižnice in obnovo zunanje kapele ter vhoda v cerkev.
Obnovitvena dela
Ker je bila cerkev v preteklosti deležena skromnih obnovitvenih del je dajala videz zapuščenost in zanemarjenosti, njen izgled je bil plod hotenj, ki jih je s seboj prineslo obdobje polpretekle zgodovine. Stanje cerkve je bilo kritično zlasti v gradbenem smislu, njena spomeniška pričevalnost pa je bila zaradi preteklih neprimernih posegov okrnjena.
O stavbni zgodovini in pomenu cerkve ni bilo veloko znanega. Tudi danes bi bilo še tako, če ne bi na pobudo Župnijskega urada iz Vuzenice stekla obsežna prenova v okviru katerih so prišle na dan zgovorne gradbene in likovne sestavine prvotne cerkvene podobe. Obnova je trajala skoraj desetletje, se pričela 1992 in končala leta 2000. V okviru obnove je bila obnovljena zunanjost, streha, na novo so bila tlakovana tla, očiščene in utrjene so bile freske, restavrirana je bila cerkvena oprema, posebne pozornosti je bil deležen glavni oltar iz leta 1666. Z rekonstrukcijo pozlate in polihromacije je oltar zopet dobil nekdanjo bleščavo.
Zanimivosti
Železniška nesreča pod Devico marijo. Nesreča se je zgodila 16. junija1898, ko je ob 4.30 zaradi zemeljskega plazu iztirila lokomotiva tovornega vlaka in z vagonom zdrsnila po strmem pobočju ter se ustavila na obrežju Drave. Kljub dramatičnemu dogodku žrtev ni bilo. Železničarji pa so v zahvalo še nekaj desetletij darovali za sveto mašo v cerkvi Device Marije na Kamnu.
Leta 2000 je bila cerkev Device Marije na Kamnu imenovana med svetoletne cerkveMariborske škofije. Na Kamensko Slomškovo nedeljo13. avgusta 2000 je škof Franc Kramberger cerkev ponovno posvetil in v glavni oltar vložil Slomškove relikvije.
