W 1859 irlandzki matematyk [[William Rowan Hamilton]] sformułował problem istnienia cyklu o długości ''n'' w grafie ''n''-wierzchołkowym{{odn|Sysło|Deo|Kowalik|1995|s=283}}.
Za faktycznegopierwszego twórcęautora, problemuktóry sformalizował matematycznie problem komiwojażera uznaje się austriackiego matematyka [[Karl Menger|Karla Mengera]], który go zdefiniował go w 1930{{odn|Sysło|Deo|Kowalik|1995|s=314}}, zwracając szczególną uwagę na stopieńtrudność w jegoobliczeniu skomplikowaniarozwiązania<ref>{{Cytuj | autor = Alexander Schrijver | rozdział = The traveling salesman and the assignement problem | url = https://books.google.pl/books?id=mqGeSQ6dJycC&pg=PA50&lpg=PA50&dq=Botenproblem&source=bl&ots=xQLOOZfpNf&sig=Q4GV-PhBgjRtatHa5A3IgoVhmpk&hl=pl&sa=X&ved=0ahUKEwiBp_Xiie7MAhWMFJoKHb3SBBEQ6AEIKDAB#v=onepage&q=Botenproblem&f=false | tytuł = Combinatorial Optimization: Polyhedra and Efficiency | s = 51 | język = en }}</ref>. Niezależnie od niego ten sam problem poruszył w 1934 [[Hassler Witney]] na wykładzie w [[Princeton University]]{{odn|Sysło|Deo|Kowalik|1995|s=314}}. Natomiast pierwszepierwsza praktycznepróba zastosowanierozwiązania problemu miałomiała miejsce w 1937, gdy Merrill Flood pracował nad rozwiązaniem wyznaczania tras dla autobusów szkolnych{{odn|Sysło|Deo|Kowalik|1995|s=314}}.
Z uwagi na bardzo prosty opis problemu oraz opiniiopinię o bardzo trudnym obliczeniowo procesie optymalizacji, problem komiwojażera stał się bardzo popularny{{odn|Sysło|Deo|Kowalik|1995|s=314}}. Fascynacja ta trwa od lat pięćdziesiątych XX wieku do dziś, zarówno wśród amatorów jak i profesjonalistów{{odn|Sysło|Deo|Kowalik|1995|s=314}}<ref name=":0" />.
