Początki Oleksowa nie są znane. Pierwsza pisana wzmianka o tej miejscowości pochodzi ze spisów parafialnych z lat 1325-1327. Wspomina się wtedy drewniany kościół i proboszcza Lamberta. Bolesław Kumor początki parafii umieszcza w XIII wieku. Brak jest bliższej daty jej powstania. Data powstania parafii w 1254, podana przez księdza Wiśniewskiego w 1913 r., nie została przez ks. Kumora potwierdzona. Początkowo parafia Oleksów związana była z archidiakonatem lubelskim. Parafia Oleksów otrzymywała dziesięciny z Bronowic (parafia Jaroszyn) i z pobliskiej Policzny. W kronikach Jana Długosza z XV wieku Oleksów zwany był też Bierdziedze. Na przełomie XIV i XV wieku wieś należała do rodziny Gnatowskich a potem przeszła na własność Gniewoszów. Historia gminy nierozerwalnie związana jest z tym rodem. Przodkami rodu Gniewoszów z Oleksowa był ród Gniewoszów herbu Rawicz z Dalowic w powiecie proszowskim w pobliżu Krakowa.