Lastovce boli osídlené už v období neolitu. Z archeologických nálezov vyplýva, že sa tu nachádzali sídla bukovohorskej kultúry, eneolitické sídla s kamelovanou keramikou. Našli sa tu žiarové hroby pilinskej kultúry z mladšej doby bronzovej, rímsko-barbarské sídlisko, vandalské žiarové hroby a poveľkomoravské sídlisko. Prvá známa správa o Lastovciach je v listine z roku 1266.
Do písomností dedinu zapisovali vo viacerých pravopisných obmenách názvu Laztouch, Lastocz, čo bol maďarizovaný tvar slovenského názvu (z,do) Lastoviec. Ten sa do písomností dostal až v 18.storočí. Pôvodný slovenský názov korenil v osobnom mene Vlasta, z toho Vlastovce a vypustením začiatočného V pod vplyvom maďarskej výslovnosti sa aj v slovenskom prostredí udomácnil názov Lastovce.
Pôvod dediny mohol byť dvojaký. Možno jestvovala už pred 11.storočím, alebo vznikla v prvej polovici 13.storočia ako zemianska osada. Obec Lastovce od 13.storočia nepretržite a aj v 17.storočí patrila tunajším zemanom. Na prelome 16. a 17. storočia boli Lastovce veľkou dedinou so zemianskym, poddanským i farským obyvateľstvom. V žiadnej inej dedine v okolí nebývalo toľko zemanov ako v Lastovciach. Vlastníkmi majetkov v obci boli okrem iných rodiny Rozvádyiovcov, Herestényiovcov, a Gerencseyovci. Sčítanie z roku 1598 uvádza 10zemepánov.
Sídlisko malo v roku 1600 obývaných 15poddanských domov, ale až 22 kúrií zemanov napokon aj kostol, faru i školu. Roku 1715 sa spomína jedna sedliacka domácnosť. V 18.storočí získavajú rozhodujúci majetkový vplyv Szirmaiovci, Kazincziovci, Bernáthovci, Isépyovci a Szemereovci. V dedine bol kostol možno pred 14.storočím,avšak písomné doklady o ňom sú od 14.storočia. V roku 1333 tu pôsobil farár menom Mikuláš. Farský kostol bol v stredoveku zasvätený Všechsvätým. Určite od roku 1598 tu pôsobili reformovaní kazatelia.
Na prelome 17.a18.storočia mali vymurovaný kostol z kameňa, ale v roku 1795 si kalvíni postavili nový a ten jestvuje dodnes. Ani našu obec neobišli tragické udalosti. V roku 1663to bola morová a v roku 1831 cholerová epidémia. Počas roľníckeho povstania na Zemplíne (1831) vznikli v obci menšie nepokoje. V rokoch 1890 až1900 postihla našu obec veľká vysťahovalecká vlna.
