Trøjborg var i slutningen af 1890’erne et udpræget arbejderkvarter, der dog endnu ikke var fuldt udbygget. Beboerne arbejde typisk på fabrik, eller de var håndværkere eller havnearbejdere. En del var også selvstændige, og på hvert gadehjørne lå der små butikker. Der var rigtig mange børn, og i weekenden tog familierne gerne ned til stranden, skoven eller ud i deres kolonihave.
Overalt var der stor byggeaktivitet, og det store antal tilflyttere havde efterhånden skabt et behov for en nordligere kirke end Vor Frue og Domkirken. Derfor besluttede Århus Byråd i 1899 at opføre Sct. Johannes Kirke på hjørnet af Aldersrovej. Kirken blev tegnet af kgl. bygningsinspektør Hack-Kampman og arkitekt Valdemar Schmidt, og den blev indviet i 1905. Hans Otto Frimodt Møller blev udnævnt som den første sognepræst i Sct. Johannes Kirken, og han var på mange måder en initiativrig og vellidt person.
I tiden efter at Sct. Johannes Kirke blev indviet, begyndte der et selvstændigt menighedsliv ud fra kirken. I løbet af kort tid tiltog arbejdet kraftigt, og venner af Indre Mission og H.O. Frimodt Møller ønskede et sted at samles til møde foruden kirken. De rettede henvendelse til Indre Missions ”Samfundsråd” i Århus, som efterfølgende besluttede at bygge et missionshus i 1906. Der blev startet en indsamling, og dannet et ”Udvalg til opførelse af børneasyl og missionshus”. Udvalget bestod af sognepræst H. O. Frimodt Møller, pastor Martin Berg, tømrermester Arnhof Thomsen og fiskehandler P. Clausen.
Det nye missionshus blev tegnet af arkitekt Frimodt Clausen, og den 27. juli 1907 blev grundstenen til Bethania lagt. Året efter blev Missionshuset Bethania indviet den 17. marts 1908 af sognepræst Busch, og huset blev tilskødet Indre Mission.