A falu nevének, -pontosabban neveinek, merthogy Batinának is nevezik,- etimológiája igen bonyolult. Több elmélet is létezik a Kiskőszeg és Batina elnevezések eredetéről. 

A római korban a Bacincum nevű település volt itt található és már akkor fontos átkelőhelynek számított a Dunán. Egyesek szerint a Batina név a Bacincumból ered. Ám itt máris képbe jön egy elmélet ami cáfolná az előbbit: Györffy György történész szerint a név a Battyánból ered. Ez azért lenne elképzelhető, mert a Duna túlpartján volt Battyán település(amely egyébként Bezdán helyén volt), s mivel már akkor volt itt révforgalom a nagy folyón keresztül ,felmerülhet, hogy a komp utasai elnevezték a túlparti falucskát kis Battyának azaz Batinának. E lehetőséggel csak annyi a gond, hogy Battyán többszáz évvel később jött létre mint Bacincum és természetesen inkább utóbbiról(mivel régebbi) eredeztethető a helységnév.

A nép a következő történetet meséli a Batina név eredetéről: Amikor az igazságos Mátyás királyunk parasztruhába öltözve járta az országot, egyszer átkelt a réven és megneszelte, hogy a kiskőszegi vár úrnője, Vörös Márta, kegyetlenül bánik a szolgálóival. Mátyás elhatározta, hogy igazságot tesz, csakhogy az úrnő megrémült a király látogatásától és hintójával a Dunába hajtott. Később azonban előkerült a folyamból a corpus delicti, ami nem volt más mint a pálca(horvátul: batina) amivel Vörös Márta az alattvalókat terrorizálta. 

Régen a falut nevezték Leányvárnak(a II. kép Leányvár omladékait ábrázolja 1893-ban) is mivel az is itt magasodott, de nem Leányvár volt a falu első vára, hanem a késő római korban(a dominátus korában, Diocletianus alatt) épült Ad Militare erőd amely a mai Szovjet emlékmű helyén állt. Leányvár, egyes 1296-os források szerint, a gazdag oligarcha család, a Kőszegiek (innen eredeztethető a Kiskőszeg név) birtokában volt, akik viszont családnevüket nem Kiskőszegről, hanem a Vas megyében található Kőszegről kapták. Később a vár átkerült a Héder nemzetségbeli, János birtokába aki 1315-ig Baranya, Bodrog, Somogy és Tolna ispánja volt.