Historia thumb|left|Pałac w Wielichowie z pocz. XIX w. thumb|Kościół parafialny pw. św. Marii Magdaleny z lat 1762-79 Historycy podejrzewali, że w okolicach miejscowości 200 metrów na południe od rynku stało wcześniej domniemane grodzisko, które jednak okazało się być naturalną formą terenową. Na kilku stanowiskach w Wielichowie archeolodzy znaleźli fragmenty naczyń pochodzących przeważnie już z pełnego średniowiecza.
Miasto kiedyś była wsią związaną pierwotnie z Wielkopolską. Osada pod tą nazwą istniała już na początku XIV wieku. Pierwsze wzmianki o niej pochodzą z 1304 oraz 1308 roku. Dokument z 1350 wystawiony przez króla polskiego Kazimierza III Wielkiego odnotował, że miejscowość była obdarzona wolnizną. Zwalniał on kmieci oraz mieszkańców dóbr biskupich, w tym m.in. Wielichowo, od świadczeń na tak długo, dopóki będą oni korzystać z wolnizny udzielonej im przez biskupa. Zwolnienia podatkowe wobec wsi stosowano podczas lokacji nowych miejscowości, a więc w tym czasie została ona prawdopodobnie dopiero niedawno założona.