Vainolaistarinat ovat osa monien kansojen kansantarustoa. Vainolaistarinoissa paikallinen väki joutuu vieraan ryhmän, vainolaisten, hyökkäyksen kohteeksi ja puolustautuu. Monissa vainolaistarinoissa paikallinen väki voittaa taikansa, rohkeutensa tai oveluutensa avulla vainolaiset. Joissain tarinoissa vainolaiset kuitenkin ehtivät tehdä pahaa ennen kuin heidät voitetaan. Usein paikalliseen väkeen kuuluu sankari, jonka avulla vainolaiset voitetaan tai karkotetaan. Sankarilla voi olla yli-inhimilliset ruumiin- tai taikavoimat.
Suomalaisten ja saamelaisten vainolaistarinat ovat usein puoli-historiallisia. Ne perustuvat löyhästi historiallisiin vainoihin ja hyökkäyksiin, mutta tarinoita on vahvasti muokattu ja väritetty. Samoja piirteitä löytyy monista kertomuksista eri puolilta Suomea, joten osittain on kyse kulkutarinoista.
Saamelaisissa vainolaistarinoissa vihollisina esiintyy useita eri ryhmiä. Tämä perustuu todelliseen historialliseen tilanteeseen, sillä useat ryhmät kilpailivat lappalaisten verotuksesta. Saamelaisten tarinoiden tsuudit on tulkittu suomalaisiksi.
Virolaisten, kuten muidenkin Baltian kansojen tarustossa vainolaisia ovat saksalaiset ja venäläiset. Muistot saksalaisista rautamiehistä liittyvät suurelta osin "pohjoisiin ristiretkiin" balttilaisia pakanoita vastaan. Virolaisesta kansantarustosta kootussa ja muokatussa Kalevipoeg-eepoksessa Kalevinpojat ja muut virolaiset taistelevat rautamiehiä vastaan tappaen lukuisia. Lopulta rautamiehet kuitenkin voittavat ja Viro joutuu saksalaisten käsiin.