Alderslyst sogns kirke blev opført i 1929. Der havde været forskellige ønsker om dens placering, idet nogle ville, at den skulle ligge nær bydelens hovedgade, Borgergade, men resultatet af mange forhandlinger blev, at man byggede den på kirkegården, som var anlagt og taget i brug i 1926.
Arkitekt ved byggeriet var Edvard Jensen, Silkeborg, og han fulgte tidens kirkebyggeskik: at rejse et kirkehus i stil med de gamle kirker. Fra gårde i Balle sogn blev der givet en del af de store sten, som danner kirkens sokkel. Et andet vidnesbyrd om tilhørsforholdet til Balle sogn har man i kirkens prædikestol, der er fremstillet af træ fra gammelt tagværk på Balle kirke. Dens udførelse er bekostet af sognets daværende præst Jens Andersen. Kalk, disk og oblatæske er skænket af direktør J. A. Nielsen Duelund og hustru, dåbsfadet af overlærer H. Skov og hustru, den ene af alterstagerne af rektor Theodora Lang og frøken A. Hølfzermann og den anden af provst Aage Bojsen Møller, Slagelse og sognepræst Anders Larsen, Jelling, begge tidligere præster i Gødvad-Balle pastorat.
I 1952 fik kirken malmlysekroner udført efter model fra Skive gamle kirke, anskaffet for penge indsamlet i sognet. Sølvvasen på alteret blev skænket af købmand Dorthea Frederiksen i 1979.