Veletiny patří k velmi starým osadám, neboť ležely na starodávné cestě vedoucí z Brna přes Bzenec, Kunovice, Sady a Podolí na Uherský Brod a dále Starohrozenkovským průsmykem do Uher. Stará pověst klade dokonce její původ do období říše Velkomoravské.

Původní osada zde byla zjištěna v místech "Losky". Pro tehdejší obyvatele Veletin, živící se většinou zemědělstvím, bylo sídlo na Loskách nepříhodné, poněvadž většina polí se nacházela na levém břehu Olšavy. Vystavěli si proto novou vesnici ve vyšší poloze, v místě dnešních Křivosúd, kde nebyly bažiny a neohrožovaly je povodně.

V roce 1141 ležela vesnice v oblasti patřící k Olomouckému biskupství, na pomezí arcijáhenství spytihněvského a bředavského. První písemná zmínka o obci je však až z roku 1201. V červenci t. r. daroval český král Přemysl Otakar I. klášteru Hradiště u Olomouce ves Štěpánov a zároveň potvrdil tomuto klášteru držbu řady vesnic, mezi nimiž se jmenuje i Veletin (Sub eisem vera sigilli ... testium supradictum, has villas confírmavi... Weletin).

Na přelomu 12. a 13. století byly tehdy Veletiny majetkem Hradišťského kláštera. Brzy na to, v roce 1205, přichází na Velehrad 12 cisterciánských mnichů z Plas a zakládají nový klášter, který byl obdarován řadou vesnic. Bylo tak založeno velehradské panství a nedlouho potom zahájena velká kolonizace krále Václava I. a Přemysla Otakara II. Zásluhou šlechtice Boreše z Rýzmburka a jeho synů byly založeny obce Němčí, Slavkov, Bohuslavice, Boršice a další. Samy Veletiny se v této době staly majetkem drobné šlechty - pánů z Veletin. Mezi svědky donace olomouckého biskupa Theodorica v roce 1283 se mimo jiné jmenují Jiljí z Veletin a Závis a Sláva z Veletin, snad jeho synové. Roku 1354 držel Veletiny Pešek z Veletin, který zemřel před rokem 1362, a po něm ves zdědili jeho synové Mikšík, Ješek, Pešek Závis a Petr. Ve svém rodném znaku měli páni z Veletin osmiloukoťové kolo. (V 17. století toto znamení užívala na své pečeti obec Podolí). Syn Peška z Veletin, Petr, se uvádí roku 1375, Pešek byl v roce 1365 ženat s Annou z Krumsína, která v roce 1371 měla na Veletinách zástavu 60 hřiven, roku 1373 držel Bílevsko a roku 1375 Vrbku. Mikšík držel roku 1365 Rychlov, 1374 Vrbku a v letech 1376 až 1407 Heršice, Ješek držel roku 1365 Moravany, roku 1371 Blevsko a Rychlov a 1384 Vrbku.

Závis, který v letech 1365 až 1406 držel Rychlov, Vrbku a Lipovou, vybudoval ve Veletinách nad Křivosúdy tvrz jako sídlo místních vladyků. Tento rod však majetek ve Veletinách ve svých rukách neudržel. V roce 1381 dává totiž markrabě moravský Jošt Veletiny lénem Ješkovi Lukovskému ze Štranberka. V roce 1389 však již Petr ze Šternberka dává Veletiny s tvrzí a mlýnem Sicgfriedu ze Slatiny.

V druhém desetiletí 15. století otřásla nejen Čechami, ale i jihovýchodní Moravou husitská revoluce. Proti upálení Mistra Jana Husa připojil svou pečeť na protestní list v září 1415 i Hereš z Veletin a Mikuláš z Heršic, spoluvlastník Veletin. Po roce 1420 se stal majitelem Veletin Dobeš z Rohozova, který patřil k rodu Bedřich ze Strážnice. Tato drobná šlechta - Bedřich ze Strážnice, Tomáš z Vizovic, Vašek z Valdštejna a na Uherském Ostrohu a další - se postavila do čela venkovského lidu v boji proti náboženskému, národnostnímu a sociálnímu útlaku. Husitské povstání na jihovýchodní Moravě s centrem na malém moravském Táboře u Nedakonic, bylo namířeno zejména proti klášteru na Velehradě. Boj však zasáhl i další oblasti - Uhersko-Brodsko, Hlucko i Vlčnovsko.

Dne 29. června 1437 vložil do zemských desek Dobeš z Rohozova vesnici Veletiny s rychtou, mlýnem, dvěma hospodami a lesy a veškerými robotami Arklebovi z Vlčnova a jeho synu Burianovi. Za spoluúčastníky těchto držav byli přizváni strýcové Zich z Lipiny a Jindřich z Chlumu. Jak Arkleb, tak Burian z Vlčnova, který zemřel ve Veletinách 29. listopadu 1460, se snažili využít všech prostředků a možností k vytvoření a rozšíření svých dědičných statků. Mimo jiné se na čas zmocnoli části majetku velehradského kláštera (Podolí), získali Vlčnov a Nový Světlov atd. Rozhodně také začali odmítat nároky svých příbuzných na Veletiny. V roce 1448 vedla proto Sibyla z Veletin stížnost na Buriana, že drží dědictví "Veletiny, tvrz, dvůr i ves" a dokonce se odvážil odprodat třetinu jejího dědičného mlýna v této vesnici. Manželem Sibyly z Veletin byl Jindřich z Morkovic, který zemřel před rokem 1483. Jindřichu Bařickému také vložil v roce 1466 potomek Buriana Jiřík z Vlčnova, samotnou ves Vlčnov. Synové Jindřicha byli Jan a Michal (připomínající se roku 1464) a Václav Bařický z Morkovic. Veletiny samé se však dostaly do rukou Petra Bílého z Hostišova, který před rokem 1480 vzal na společné vlastnictví Veletin Dobiáše z hory Obřanské.

V letech 1480 -1484 seděl na veletínské tvrzi velitel "černé roty" Petr Haugvic z Biskupic. Ten prodal Veletiny Mikuláši Čečvickému z Lužic. Svého práva však na Veletiny a další statky dosáhli Morkovicové, neboť 6. ledna 1492 vložili do zemských desek odprodej Sibyla a Perchta z Morkovic, dcery a dědičky Václava z Morkovic, které prodaly Veletiny s dvorem a Vlčnov, Kvačice, Chylice a Hradčovice Přibíku ze Zahrádky. Dne 24. června 1499 byl tento majetek prodán Vilému Hřivinovi z Újezda a v roce 1504 Burianu z Vlčnova, který je prodal roku 1518 Janu z Kunovic.

Tím byly Veletiny připojeny k panství Uherský Brod, s kterým sdílely majitelé i osudy až do roku 1850. Pánové z Kunovic (Jan 1506 - 1545, Jetřich 1545 -1582, Arkleb 1582 -1609, Jetřich a Jan 1609 -1610 a Jetřich 1610 -1611) prodali v roce 1611 statek Kounicům.