Pierwsze zachowane dokumenty nie wspominają o Tuszymie wprost. W roku 1379 Jan z Tarnowa zakupił od braci Piotrasza, Mikołaja i Budka (z Budziwoja), dziedziców z Bobina ich wieś Kościelów (Cosczelow) w ziemi Sandomierskiej. Z późniejszych danych wynika, że leżała ona w parafii Rzochów. Rejestry poborowe wymieniają ją jako wieś płacącą podatki łącznie z Tuszymą. Kodeks dyplomatyczny Małopolski informuje, że w 1379 roku Jan z Tarnowa uzyskał od królowej regentki Elżbiety zgodę na przeniesienie swoich wsi: Zochów (tj. Rzochów), Trześń, Bełk oraz Kościelowa z prawa polskiego na magdeburskie. W roku 1413 istnieje i po raz ostatni jest wymieniany Kościelów Mały. W późniejszym czasie, zapewne wszedł on w skład samego Kościelowa a z czasem i do Tuszymy, z którą sąsiadował po jej wschodniej stronie. Ostatnia znana wzmianka o Kościelowie pochodzi z 1721 roku.
Lokacja na prawie niemieckim dostarcza kolejnych wzmianek o Tuszymie. Oprócz dokumentów lokacyjnych są liczne wzmianki o sołtysach. Pierwszym sołtysem, wymienionym w roku 1411 był Zygmunt.