Rodowód Leliwitów zajmował wielu historyków, poczynając od Jana Długosza, aż po wiek XX. Istnieją na ten temat dwa odmienne poglądy: Spicymir miał być przybyszem znad Renu, albo też rdzennym Słowianinem. Rozbieżne opinie dotyczą również pochodzenia herbu Leliwitów "niepełnego księżyca z gwiazdą w polu niebieskim".
Zwolennicy obcego pochodzenia Leliwitów, do których należał Jan Długosz, wywodzą nazwę herbu "Leliwa" od zamku Mondstern nad Renem, skąd miał przybyć protoplasta tego rodu w Polsce. Samą legendę herbową Długosz przedstawił w kilku wersjach. W "Clenodiach" czytamy, iż Spicymir przybył znad Renu za czasów "Władysława I króla polskiego i zarzucił swe pierwotne godło Ogniwo, bowiem złączył się z rodem polskim mającym w herbie ubywający księżyc jaśniejący z gwiazdą jaśniejącą".
    W  Liber  Beneficjorum,  ten  sam  Długosz  inaczej  przedstawił  rodowód  Leliwy.  Pisząc o fundacji Kościoła tarnowskiego, wspomniał, iż

" ... wtedy właśnie ród szlachecki Leliwitów wywodzący się znad Renu, z krwi Alemanów, mający jako znak herbowy gwiazdę sześcioramienną otoczoną dwoma rogami   księżyca   na   niebieskim  tle,  opuścił  własne  dotychczasowe  siedziby i mając szczęśliwiej zamieszkać, wszedł do ziem Królestwa Polskiego".

    Więcej na ten temat powiedział pisząc o kościele p.w. Wszystkich Świętych w Krakowie. Ów kościół miał być wybudowany i uposażony przez niejakiego Jakuba Bobolę

" ... dzielnego rycerza bardzo pobożnego i religijnego, który na mocy złożonego ślubu używał w ubiorze zewnętrznym zarówno on sam jak i jego rodzina grubego sukna, wyłącznie koloru białego... Tenże Jakub nosił na orężu i tarczy ogniwo długie a wąskie. Jego liczni potomkowie połączyli się z rycerzami i wielmożami, jacy przybyli znad Renu, a mianowicie tymi z Tarnowa, Melsztyna i Jarosławia, mającymi jako herb Księżyc niepełny z gwiazdą w polu niebieskim. W wyniku tego połączenia, porzuciwszy starodawny znak, tj. owe Ogniwo, zaczęli używać jako herbu, księżyc niepełny wraz z gwiazdą. Istnieje także przekaz, jakoby wspomniany ród i dom, który dotąd nazywa się "Leliwa", nie przybył znad Renu, ani też stamtąd nie przyniósł księżyca z gwiazdą jako herbu, lecz po jakiejś szczęśliwej i zwycięskiej bitwie z Węgrami, w której walczono aż do pojawienia się księżyca i gwiazd (jako że , był wówczas księżyc niepełny), został w dowód okazanego wówczas męstwa nagrodzony przez Władysława Łokietka, króla polskiego".

    Zwolennikiem polskiego pochodzenia Leliwitów był biograf hetmana Jana Tarnowskiego - Stanisław Orzechowski - który pisał:

"Ród domu Tarnowskiego ani gościem. ani przechodniem w Polszcze nigdy u nas nie był, jako niektórzy pod kądzielą siedząc między babami powiadają, iż Leliwa z Niemiec, od Renu do Polski przybyła - co nie jest. Albowiem Leliwa tak polskim herbem zawsze była, jako jest Starza, Srzeniawa, Tramki, Jastrzębiec, Łódź, Odrowąż, Nałęcz i inne polskie herby - a to może być pokazano starodawnemi przywilejami polskimi i ruskimi".

    Pochodzenie herbu, Orzechowski uważa za rodzime, słowiańskie, stwierdzając, że w swym zawołaniu znaczy tyle, co "patrzwa sam". Dalej pisze o Leliwie że,

"z przygody jakiej wielkiej się urodziła. Musiał być przodek herbu tego ktoś dzielny, w którym ludzie w ostatnich przygodach po słowiańsku się tak cieszyli: patrzwa sam, jeśli wybrnąć chcemy".

    Autor również inaczej opisuje samą Leliwę, która według niego nie jest półksiężycem lecz półkolem.

" ... Niechajże tamci nad Renem Niemcy mają sobie miesiąc i gwiazdę swą, który znakiem oni rodzoną krew naszą polską przywłaszczają sobie. Rzeczywista Leliwa to nie księżyc i gwiazda, jeno obraz połowy koła, herb od prostoty onej dawnej polskiej idący (...), bo szlachectwa polskie z ludzi prostych poszły".

    Za nadreńskim pochodzeniem Leliwitów opowiadał się w "Gnieździe cnoty" Bartosz Paprocki, który pisał:

"Za króla Władysława Rycerz doświadczony
Spicymierz zajechał tu w tego państwa strony,
Wielka godność y skarb z sobą przyprowadził
Miast, wsi wiele, nakupił i pustyń osadził:
Dla których dziś potomstwa jest wiele możnego
W okrąg tego sławnego Królestwa Polskiego
I tak się przypatrzywszy kleynotu własności
Przypatrz się tey szerokiey potomstwa zacności". 

    Kacper Niesiecki w "Herbarzu polskim" wywodzi Leliwitów znad Renu, z zamku Mondsztern. Do Polski Spicymir miał przybyć za czasów Władysława Łokietka. Podał też historię tłum. łaski jakimi Król ten obdarzał Leliwitów:

" ... Gdy ten monarcha z tronu wyzuty, i z ojcowizny wypędzony, cudze kraje potyrać musiał trafił nad Renem na ojca Spicymirzowego, któremu, gdy się poufale  zwierzył,  godności  w  sobie  utajonej  i  niedoli,  że  z  ojczyzny, fortuny i tronu,  wyrzutkiem  został,  od  tego  mile  przyjęty,  srodze  przez czas niemały w  domu  u  siebie  był  traktowany. Wdzięczny tej łaski Łokietek, bo gdy się burza w Polsce na niego ugłaskała, a on do zupełnej i spokojnej possessyi korony przyszedł, jednego z synów swego dobrodzieja, to jest Spicymira do Polski wprowadził, w dobra obszerne  opatrzył, w honory wyniósł i w kolligacyą z sobą ...". 

    Wiele uwagi poświęcił Leliwitom historyk XIX-wieczny, Franciszek Piekosiński, Ród Leliwitów wywodził od rycerza Tarna żyjącego w VI wieku. Spytko, kasztelan krakowski, założyciel Tarnowa, miał być prawnukiem opisanego przez Długosza Jakuba Boboli, wnukiem bliżej nie znanego Spicymira, a synem Jakuba Spicymirowicza, kasztelana wiślickiego. Podanie o nadreńskim pochodzeniu Spicymira uważał za legendę bez pokrycia.
Legendą  herbową Leliwitów  i  ich  pochodzeniem  zajmowali  się również autorzy monografii o Tarnowie. Wincenty Balicki oraz Jan Leniek starali się uzasadnić ich rodzime pochodzenie. Takiego zdania jest również historyk współczesny, autor dzieła "Leliwici tarnowscy" - Włodzimierz Dworzaczek.

    Być może rację ma Jan Leniek, iż herb Tarnowskich Leliwa przedstawia księżyc na nowiu, gdy nad nim znajduje się gwiazda Wenus i powstała po jednej z bitew stoczonych z Węgrami przez wojska Władysława Łokietka, w czasie której na niebie pojawił się księżyc z gwiazdą ponad nim. Król miał uznać to za wróżbę zwycięstwa i dlatego nadał znak ten jako herb, rodowi, który najbardziej odznaczył się w tej bitwie.