Sredi Šaleka stoji pod gradom zgledno obnovljen najlepši velenjski kulturni spomenik, nastal v obdobju med gotiko in barokom - cerkev sv. Andreja (11). Postavili so jo med letoma 1510 in 1516, v virih je prvič omenjena leta 1545, leta 1631 pa je bila kdo ve zakaj imenovana kot cerkev sv. Krištofa in Andreja pod šaleškim gradom. Ko so ji v 17. stoletju prizidali zvonik in v drugi polovici 18. stoletja stranski kapeli, je cerkev popolnoma spremenila zunanji videz. Ljubitelje lepega navdušujejo poznogotske in zgodnjerenesančne poslikave cerkvene zunanjščine, na zunanji strani pa je vzidan tudi nagrobnik iz leta 1626. Čeprav je to uradno še vedno velenjska podružnična cerkev, ki sodi pod župno cerkev sv. Martina (10) v severnem delu mesta, je zdaj v resnici šaleška župna cerkev blaženega Antona Martina Slomška; cerkveni patron sv. Andrej že dolgo stoji v stranskem oltarju, sv. Vid je prostor na prekrasno rezbarjenem glavnem oltarju prepustil slovenskemu svetniku Slomšku, tretji oltar iz leta 1767 pa je posvečen sv. Erazmu. Ko so leta 1991 urejali cerkveno okolico in prinesli v zvonik nove zvonove, so neznanci iz Erazmovega oltarja ukradli dva kipa; doslej ju še niso našli. Najstarejši cerkveni zvon z letnico 1505, ki so ga prinesli iz šaleškega gradu in je do leta 1991 zvonil iz cerkvenih lin, je zdaj shranjen v zakristiji. O starosti cerkve govori med drugim letnica 1510 takrat so verjetno prezidali cerkev, ki jo krasijo prelepi rebrasti oboki nad oltarjem, ladjo in korom, ljubitelje lepega pa navdušuje tudi zgledno urejena zunanjost cerkve in njene okolice.