Pierwsze poświadczone przez archeologów ślady pobytu ludzi w rejonie dzisiejszych Klementowic pochodzą z paleolitu, czyli starszego okresu epoki kamienia i datowane są na czasy między XIII a XI tysiącleciem p.n.e. W Klementowicach-Kolonii odkryto kilka tysięcy różnorodnych zabytków krzemiennych, stanowiących pozostałość po obozowisku łowców reniferów sprzed blisko 13 tys. lat (okres tzw. kultury magdaleńskiej). Jest to jedno z najciekawszych stanowisk archeologicznych na ziemiach polskich wiązanych z kulturą magdaleńską oraz najdalej w kierunku północno-wschodnim wysunięty punkt osadnictwa tej kultury w Europie.
Prace wykopaliskowe prowadzone w Klementowicach dostarczyły także szczególnie istotnych danych do badań nad neolitem – młodszym okresem epoki kamienia, który na Lubelszczyźnie rozpoczął się wraz z początkiem V tysiąclecia p.n.e. Ówcześni mieszkańcy naszych ziem znali już sposoby uprawy ziemi, umieli hodować zwierzęta, lepić i wypalać naczynia gliniane, wykorzystywano naturalne włókna roślinne i zwierzęce, przędąc je i tkając. Udoskonalono techniki obróbki surowców kamiennych. Zakładano małe osady.
Pod koniec IV tysiąclecia p.n.e. pojawiły się na obszarze Klementowic społeczności identyfikowane przez archeologów z kulturą pucharów lejkowatych. To czasy intensyfikacji gospodarki rolno-hodowlanej; zwiększeniu uległ areał pól uprawnych, na dużą skalę wypalano lasy użyźniając glebę popiołem, zaczęto także używać radła ciągniętego przez woły. Podczas wykopalisk odkryto niewielką osadę oraz osiem cmentarzysk. Na podstawie odnalezionych fragmentów ceramiki udało się odtworzyć szereg naczyń, min. pucharów, kubków, amfor i waz. Odnaleziono bardzo starannie oszlifowane siekierki krzemienne, kamienne toporki, narzędzia z kości, gliniane przęśliczki. W grobach pod gruba warstwą brył opoki (czasem stwierdzano także obecność innych konstrukcji kamiennych), znajdowano najczęściej pojedyncze pochówki szkieletowe bez wyposażenia, rzadziej zawierające do kilku darów w postaci naczyń, narzędzi czy ozdób.
W końcowej fazie neolitu, około połowy III tysiąclecia p.n.e. przybyła na tereny dzisiejszych Klementowic ludność kultury amfor kulistych. Podstawą gospodarki owych plemion był pasterski chów dużych stad bydła. W Klementowicach odnaleziono groby pochodzące z tego okresu. Do konstrukcji grobów używano zazwyczaj kamieni wapiennych. Zmarli wyposażeni byli w naczynia, całkowicie oszlifowane ozdoby krzemienne, czasem także amulety z zębów dzika, groty kościane, paciorki bursztynowe. Niekiedy do grobów składano też ofiary z ludzi lub zwierząt.