Planung und Bau des „Neudeggertempels“ wurden privat finanziert, das Grundstück in der Neudeggergasse stammte aus der Verlassenschaft von Moritz Königswarter, der lange davor schon den Bau des Stadttempels großzügig unterstützt hatte. Der Architekt Max Fleischer wurde 1897 mit der Arbeit für die Synagoge in der Josefstadt betraut. Es dauerte allerdings sechs Jahre bis zum Baubeginn, da das Ansuchen mehrere Male alle behördlichen Instanzen passieren musste. Der Brand des Ringtheaters 1881 hatte diese vorsichtiger werden lassen. Dass man erst klären musste, dass eine Synagoge kein Theater ist, beschleunigte das Verfahren natürlich nicht. Der Verwaltungsgerichtshof stellte schließlich fest, dass eine Synagoge tatsächlich kein Theater sei und man konnte mit dem Bau beginnen. Die Grundsteinlegung erfolgte im Februar des Jahres 1903, nach sechs Monaten konnte die Synagoge ihrer Bestimmung übergeben werden.