Dnešní radnice má hluboké kořeny v městské minulosti. Kyjov vlastnil klášter Hradisko u Olomouce až do roku 1539, kdy jej prodal. Po několika vlastnických změnách se v roce 1548 město dostalo do rukou České komory za devět tisíc zlatých. Rozhodnutí císaře Ferdinanda I., kterého o navrácení města požádala deputace vedená Václavem Bzeneckým starším, se zásadně promítlo do dalšího vývoje. Bzenecký se stal prvním primátorem a v průběhu svého vedení (1548–1575) inicioval ekonomický a stavební rozvoj města. Začaly se stavět kamenné obranné věže, vznikla sladovna a náměstí bylo vydláždě­no. Vrcholem tohoto rozkvětu byla výstavba radnice v letech 1561–1562, kterou provedli italští stavitelé a kameníci pracující v té době na Moravě. Podle záznamů zde byla usazena nejméně šestice italských rodin ještě v roce 1577. Stav budovy připomínající Bzeneckého zasluhy zůstal zachován na pamětní desce umístěné nad vstupem.

Stavba prošla během staletí mnoha přestavbami a byla opakovaně poničena požáry. V roce 1582 byla věž zvýšena a opatřena novým krytem s rakouským orlem na vrcholu. Požáry z let 1679, 1701 a 1721 ji vážně poškozovaly. Po velkém požáru roku 1876 byla věž vybavena novou renesanční bání podle návrhu vídeňského profesora Karla Königa, kterou za čtyři tisíce šest set zlatých realizoval místní stavitel Václav Paterna. Během staletí se radnice stala součástí městské správy a soudnictví – od roku 1868 zde sídlil okresní soud, později se připojila věznice a popraviště.

V sedmdesátých letech dvacátého století proběhly zásadní stavební úpravy. Byla obnovena původní renesanční fasáda, ve sklepeních vybudována radniční vinárna a vznikl nový radniční balkon. Tento balkon se stal místem pro slavnostní projevy – 8. března 1990 zde hovořil prezident Václav Havel. Na počátku nového tisíciletí byl před plánovaným rozšířením proveden archeologický průzkum, který odhalil stopy osídlení od jedenáctého století, zejména zbytky srubu z první třetiny jedenáctého století a keramiku ze střední doby. Nový zadní trakt dostavěn v roce 2001 obsahuje kanceláře, zasedací místnost pro městskou radu a radniční galerii. Součástí komplexu je také kruhová kašna navrhnuta městským architektem Vladimírem Vašíčkem. Radnice dnes představuje součást městské správy a kulturního života, chráněna jako národní kulturní památka.