1930’lu yılların ikinci yarısında Anıtpark yapılmış, Utku Abidesi (Zafer Anıtı) dikilmiş ve sıra görkemli bir belediye binası yapmaya gelmiştir. O dönemde günümüzde Zafer Müzesi olarak kullanılan bina, belediye binası olarak hizmet vermektedir ve ihtiyaca cevap verememektedir. 
O tarihte Afyon Belediye Başkanı olan Hüseyin Tiryakioğlu, devrin Nafia Vekili (Bayındırlık Bakanı) hemşehrimiz Ali Çetinkaya’nın da destekleriyle bir şehirleşme hamlesi başlatılır. Zafer Abidesi’nin arkasında bulunan ev ve arsalar istimlak edilerek Cumhuriyetin 14. Kuruluş yıldönümü olan 29 Ekim 1937’de belediye binasının temeli atılır ve inşaat başlar. Yeni belediye binasın bu alanda inşa edilmesindeki amaç:  modern bir şehri temsil eden Anıtpark ve burada yer alan Utku Anıtı’nın arkasındaki şehrin eski dokusunu saklayarak güzel bir dekor oluşturmaktır. 
56.818 TL keşif bedelli binanın yapım işini İzmirli Mimar Kemal Tetik üstlenir. Mimar Kemal Bey aynı dönemlerde ilimizde pek çok kamu binasının da mimar müteahhitliğini üstlenmiştir. Kız Meslek Lisesi, PTT Binası, şimdi yerinde 1. Belediye Çarşısı olan Sebze Hali onun eseridir. 
Yeni yapılan binanın Belediye’nin bütün ihtiyaçları göz önünde bulundurularak uzun yıllar hizmet vermesi amaçlanmıştır. 
Belediye ve Kız Enstitüsünün Yapım Aşaması 
1.Katta 15 oda, 2. Katta 176 metrekare genişliğinde halkında görüşmeleri izleyebileceği bir Meclis Salonu, encümen Odası, Başkan Odası, Sekreter Odası, Özel Görüşme Odası, Büfe gibi kısımlar, 3. Katta ise şehrimizi ziyaret edecek önemli kişilerin kalabileceği banyolu odalar bulunmaktadır. İtfaiye kısmında ise araçların girip çıkabileceği kepenkli bir garaj, itfaiye erleri için yatakhane, yemekhane, salon, 3 tane idari oda gibi ayrıntılara yer verilmiştir. 
56.918 lira keşif bedelli binanın 1 yıl içerisinde bitirilerek 1938 yılında hizmete açılması amaçlansa da çeşitli sebeplerden dolayı bir süre epey uzamıştır. Bina iş bitiminde yaklaşık 90.000 liraya malolmuştur. 
Keşif bedelindeki bu artışın ve gecikmenin en büyük nedeni ise bulunduğu alanın kayalık olması ve haliyle temel çalışmalarının zor olmasıdır.
1937 yılında başlayan inşaat sona yaklaşmışken, Aralık 1939’da binanın mobilyalarının yaptırılması için Belediye Encümen kararı alınır.
Binanın mefruşatı İstanbul Beyoğlu’nda dönemin ünlü mağazası Kalinikos’tan alınır. Kararın devamında işin 29 Mayıs 1940 tarihine kadar bitirilerek teslim edilmesi imza altına alınmıştır. 
1940 yılı Ocak ayının ilk günlerinde şehrimizde bir de yabancı konut bulunmaktadır. Macar heykeltıraş Zıczek Caroly Utku Anıtı’nın ilk yapılışında var olan ve Atatürk’ün 1937 Kasım’ındaki Afyonkarahisar ziyaretinde görüp “çok büyük olmuş, anıtın görkeminin önüne geçmiş” dediği “Heinrich Krippel-Viyana” yazısının üzerini kapatması için ilimize davet edilmiştir. 
Heykeltıraş Caroly’e bir yandan yazı siparişi verilirken diğer yandan yeni belediye binasının Meclis Salonu’nda başkan kürsüsünün arkasına konulmak üzere Atatürk’ün büyük bir rölyef ve iki adet meale şeklinde rölyef sipariş edilir. 

Yaklaşık üç yıl süren inşaat 1940 yılı ortalarında bitirilir ve taşınma hazırlıklarına başlanır. Eski Belediye Binası’nın (Bugünkü Zafer Müzesi) bir müze ve kütüphane olarak düzenlenmesi gündeme gelse de bu fikrin kısmen gerçekleşmesi için 1990’lı yılları beklemek gerekir. 
Açılış için devrin Ulaştırma Bakanı Ali Çetinkaya ve şehrin ileri gelenleri davet edilir. Bir defaya mahsus olmak üzere meclis salonunda yemek verilmesi kararlaştırılır. Ve bu davet organizasyonu için İstanbul’da dönemin en ünlü oteli olan Tokatlayan Oteli ile anlaşılır. Davetten önce Tokatlayan Oteli personeli ve gerekli eşyalar İstanbul’dan trenle getirilerek açılış akşamı deneyimli garsonlar nezaretinde Belediye Meclis Salonunda bir yemek verilir. 
Tarihi belediye binası 70 yıl bu şehre hizmet verdikten sonra 2010 yılı içerisinde boşaltıldı ve Afyonkarahisar Belediyesi olarak kullanılan bugünkü binaya geçildi. Yıllarca nice mutlu anılara tarihi kararlara şahitlik eden meclis salonuyla, dönemi yansıtan mimarisiyle ve daha nice ilklerle hafızalarımızda yer eden bina artık ilginç bir tevafuk eseri olarak 29 Ekim 2014 tarihinden itibaren kent meydanı hazırlıkları kapsamında yıkılan hükümet konağının yerine Afyonkarahisar Valiliği olarak hizmet vermeye başlamıştır. 

 

Binanın ilk Valisi Hakan Yusuf Güner olurken ilk konuğu da dönemin Başbakanı Ahmet Davutoğlu olmuştur.