Szalejów Dolny po raz pierwszy w dokumentach pojawił się w 1269 r. Był to dokument biskupa Jana II z Pragi określający wieś jako siedzibę dziekana. 7.02.1350 r. wieś nabył arcybiskup Arnoszt z Pardubic, a król Karol IV zatwierdził tę transakcję.
Wchodząc na teren kościoła św.św. Szymona i Tadeusza przez boczną furtę, na jej kamiennym zwieńczeniu łukowym znajduje się herb. Jest to jedyny zachowany na terenach dawnego Hrabstwa Kłodzkiego herb rodu z Pardubic. Herb powstał w 1567 roku z inicjatywy ówczesnego proboszcza Johannesa Laurentiusa.