O powstaniu Tolkmicka mówią już legendy. Według jednej z nich gród założył pruski władca Hoggos, nadając mu nazwę Tolko. Schedę po nim przejęła jego mądra córka Mita i odtąd zamek Hoggosa nazywano Tolko Mita (Tolkmita). Inne podanie łączy miasto z rodzeństwem Tolko i Mitą mieszkającymi w grodzie Wały Tolkemita. Osieroceni , wychowywali się sami w ogromnym zamku, a pożywienie dostarczał im czarny kruk. Gdy Tolko zmarł w wyniku nagłej choroby, Mita opuściła zamek i wkrótce również zmarła w pobliskim lesie.

Badania archeologiczne dowodzą, że osadnictwo istniało tu już we wczesnej epoce żelaza (VII-V wiek p.n.e.), o czym świadczą zachowane ślady prasłowiańskiej kultury łużyckiej. Do XIII wieku bytowały tu z kolei plemiona pruskie, podbite w latach 1233-1283 przez Krzyżaków. W 1296 roku osada otrzymała przywilej lokacyjny, a jej oficjalna nazwa brzmiała wówczas Tolkemit. W 1351 roku przywilej ten został odnowiony przez Wielkiego Mistrza krzyżackiego Henryka Dusemera. W 1440 roku Tolkmicko weszło w skład Związku Pruskiego skierowanego przeciw Zakonowi Krzyżackiemu, a w 1454 burmistrz miasta złożył przysięgę wierności królowi polskiemu.

Po wojnie trzynastoletniej Tolkmicko ostatecznie weszło do granic Polski, gdzie pozostawało do I rozbioru polski w 1772 roku. W XVII i XVIII wieku miasto trawiły dotkliwe pożary, wielkie szkody poczyniła też epidemia dżumy w 1710 roku, która uśmierciła połowę jego mieszkańców.

Po roku 1772 Tolkmicko należało do Królestwa Pruskiego. Wybudowano tu nowy ratusz i pierwszą szkołę, w której w XIX wieku funkcjonował Sąd Ziemski i Miejski. W drugiej połowie XIX wieku nastąpił intensywny rozwój gospodarczy. W latach 1862 – 1883 wybudowano port, w 1873 roku poprowadzono z Elbląga szosę, w 1899 roku oddano zaś do użytku linię kolejową. W latach dwudziestych XX-wieku poprowadzono w mieście sieć kanalizacji burzowej, a w 1939 roku wybudowano fabrykę marmolady. Zniszczone w wyniku II wojny światowej miasto zostało włączone ponownie do granic Polski i powoli odbudowane.