Matejovce sa prvýkrát spomínajú v listinách z roku 1251. Meno vzniklo pravdepodobne podľa jedného z patrónov, o čom svedčí erb z 15. storočia. Obec patrila do Spoločenstva spišských sasov. V rokoch 1412 až 1772 bola obec v zálohu Poľska.
   
Pôvodní obyvatelia Matejoviec sa zaoberali zväčša poľnohospodárstvom. Podstatná zmena v živote obyvateľov nastala v roku 1845, keď tunajší rodák Karol August Scholz založil dielňu na výrobu česadiel na kone. V roku 1903 začala v obci pracovať smaltovňa. Od roku 1969 je v Matejovciach závod na výrobu automatických práčiek.
   
V Matejovciach sa nachádza gotický kostol sv. Štefana kráľa, postavený v prvej polovici 14. storočia.