Man ska inte förledas tro att de första nybyggarna i Vallsjärv kom till trakter där människan aldrig satt sin fot. För visst har det funnits människor i trakterna kring Vallsjärv långt innan Gustav Vasa bestämmer sig för att skatta bönderna.

Riksantikvarieämbetets fornminnesinventering 1993 visar förekomst av kokgropar och boplatsvallar vid Lillsandudden på sjöns västra strand. Mittemot Lillsandudden finns ett mycket fint område med flera olika fornlämningstyper. Från en kallkälla uppe på Vallsbergets västra sida löper ett 320 meter långt fångstgropsystem med ett tiotal fångstgropar. Ute på udden finns ett rikt fornlämningsområde med två stora, nästan meterdjupa rektangulära boplatsgropar. Groparna är 7×3,5 respektive 4,5×2,5 meter stora.

Inom området finns dessutom ett femtontal mindre, runda och ovala, boplatsgropar i varierande storlekar samt lämningar efter redskapstillverkning och matlagning i form av avslag, brända ben och skärvsten, dvs söndersprängda stenar som upphettats och används vid matlagning. Dessa boplatsgropar kan vara mellan 1.000 – 6.000 år gamla, men eftersom inga vetenskapliga undersökningar genomförts kan inget sägas om deras ålder.

Boplatsgropar finns även söder om Inre Tyckberget. Där har man i mitten av 1990 talet grävt fram en 6.500 år gammal grav (s k rödockragrav). Om man svänger in på Dammibergsvägen vid Furon, finns det idag skyltar som visar var stenåldershyddorna fanns samt graven som också är utmärkt med en skylt.

Dessutom finns rester efter ett antal samiska visten i trakterna kring Vallsjärv. 1949 hittade Artur Larsson, Tyckberget, en skida vid nyodling i Slätmyren. Skidan har daterats till tidigast järnålder (ca 2000 år gammal således). I området mellan Vallsjärv och Gärdforsberget finns ett stort område med fångstgropar. I Sanningslandet, fågelvägen ca tre mil från Vallsjärv, finns en av Norrbottens mest kända stenåldersboplatser.

Det kan alltså slås fast med stor sannolikhet att Vallsjärv och trakterna däromkring har varit känd av människor sedan flera tusen år. När inlandsisen smälte för ca 10.000 år sedan låg Vallsjärv vid kusten. Säljägare och fiskare bodde sannolikt där, åtminstone under sommarhalvåret, för att ta del av naturens rikedomar. För drygt 6.000 år sedan var Svartberget en lång udde som sträckte sig ut i havet, med goda förutsättningar för sälfångst och fiske. Landhöjningen, som idag är nästan en meter per århundrade, har idag flyttat kustremsan till dess nuvarande gräns vid Bottenviken, men man kan fortfarande se spår efter havet om man följer vägen förbi Beski och ser de renspolade klipporna på Svartbergets östra kant intill vägen.

Var dessa stenåldersmänniskor bofasta året runt? Om detta vet vi mycket lite, framför allt eftersom några metodiska utgrävningar inte har gjorts. I Lillberget vid Gyljen – fågelvägen ca tre mil från Vallsjärv – har utgrävningar visat att en bofast koloni har funnits på stenåldern med härstamning från den östfinska/ryska kamkeramiska kulturen (de kammade sina keramikkärl så att de fick ett vågformat mönster – därav namnet), och sannolikt skulle en utgrävning av Vallsjärvs fornfynd ge liknande resultat, men detta kan man bara spekulera kring.

Forskarna är idag ense om att det gamla påståendet att Norrbottens inland låg öde – endast befolkat av kringströvande samer – innan det togs i bruk av svenskar som trängde upp genom landet, inte är sant. Vi vet idag att människor har bott i Norrbottens inland och därmed också i nuvarande Överkalix kommun, sida vid sida med det folk som senare blev samerna, lika länge som människor trampat övrig svensk mark.