Określenie podolski złodziej występuje w wyrażeniu porównawczym ktoś ma nogi (buty) jak podolski złodziej, tzn. 'ma bardzo duże nogi (buty)'. W Słowniku porównań Mirosława Bańki znalazło się natomiast wyrażenie ma ktoś stopy jak podolski złodziej wraz z informacją, że jest to „jedno z licznych i w większości już zapomnianych powiedzeń odzwierciedlających stereotypy etniczne dawnej Rzeczypospolitej. Znane w dwóch wersjach, z których jedna odnosiła się do Podola, a druga po Polesia.” (s. 80).
Punkt wyjścia do powstania analizowanego frazeologizmu stanowiły charakterystyczne dla tego regionu ciężkie, duże buty, podkute olbrzymimi podkowami, robione ze skór podolskich czabanów, zwane pospolicie Cabanami. Por. np. obrazek: „Strasznie niezgrabnie wygląda […] podsadkowaty, krępy chłop podolski w ogromnych, ciężkich butach z olbrzymimi podkowami, w burym obwisłym sieraku lub białym lnianym kaftanie, przepasanym szerokim pasem skórzanym…” (Walery Łoziński, 1938-1861, Proces o dziwotwór). Modyfikację frazeologizmu polegającą na zastępowaniu wyrazu buty przez nogi czy stopy łatwo wytłumaczyć bliskością desygnatów (i znaczeń wyrazów).
Pozostaje jeszcze sprawa (podolskiego) złodzieja. Otóż wydaje się, że te wielkie, ciężkie, skórzane, podkute dużymi podkowami byty szczególnie rzucały się w oczy, gdy był w nie ubrany uciekający złodziej. Dlatego też one stały się podstawą porównania.
Warto jeszcze dodać, że nie mniej niż buty podolskiego złodzieja znane były dawniej podolskie pasieki, podolskie sieci i podolskie babki (z ciasta drożdżowo-biszkoptowego).