Die unteren Turmteile der Kirche stammen noch von einem Vorgängerbau aus romanischer Zeit. Das Patronat bezieht sich auf den heiligen Benignus von Dijon, einem aus Kleinasien stammenden Missionar und Märtyrer.

1419 wurde die heutige Kirche erstmals erwähnt. Es handelte sich offenbar um eine einschiffige Saalkirche mit dreiseitig polygonalem Ostabschluss, der westlich der ältere Turm vorgelagert war. 1470 (Bauinschrift) wurden Umbauten vorgenommen.

Während der Reformationszeit wurde die Kirchengemeinde evangelisch. 1551 (Bauinschrift) erfolgte ein weiterer Umbau. 1650 wurden Schäden infolge des Dreißigjährigen Krieges beseitigt. 1699 erhielt der Turm seine heute noch vorhandene welsche Haube mit Laterne. 1716 wurde das Kirchenschiff unter Einbeziehung älterer Bauteile als Saalkirche neu erbaut. Sie erhielt innen eine dreiseitige zweigeschossige Empore, deren Pfeiler ein Spiegelgewölbe tragen.

1950 kam Bischleben mit St. Benignus zum Erfurter Stadtgebiet. 1957 wurden drei neue Glocken gegossen und im gleichen Jahr vom damaligen Thüringischen Landesbischof Moritz Mitzenheim feierlich geweiht. Damals gehörte Bischleben zum Kirchenkreis Gotha.

1961 erfolgte der Einbau einer neuen Orgel. 1983 wurde der Innenraum neu ausgemalt, ein neuer Außenputz erfolgte 1987. 1993 wurden Kirchendach und Turm neu eingedeckt. 2005 erfolgten weitere Außenrenovierungen.