Parafia ewangelicko-augsburska powstała w Lesznie w 1628 r. wskutek ucieczki luteranów z Góry na Dolnym Śląsku. Exodus spowodowany był kontrreformacją i wojną trzydziestoletnią.
Pierwszy drewniany kościół został wzniesiony w 1633 r., poświęcony w 1635 r. Spłonął w pożarze miasta w 28.04.1656 r. Drugi kościół spłonął w kolejnym pożarze Leszna 19.07.1707 r. Trzeci kościół wzniesiono w 1716 r., ale 2.06.1790 także i ten budynek spłonął. Czwarty kościół został poświęcony 9.06.1805 r. Trud ciągłego odbudowywania kościoła ewangelicy leszczyńscy porównywali do męki pańskiej określając to jako krzyż, który przyszło im nieść. Stąd w nazwie kościoła zawarto te dwa znaczenia słowa „krzyż”.
W 1909 r. kościół otrzymał wieżę, którą w czasach kontrreformacji nie wolno było ukończyć.
Po II wojnie światowej kościół ewangelicko-augsburski zrzekł się prawa do budynku. Do lat osiemdziesiątych XX w. był użytkowany przez parafię polskokatolicką, następnie został przekazany rzymskim katolikom.
Najsłynniejszą postacią parafii luterańskiej w Lesznie był ks. Johann Heermann, poeta-duchowny, pochowany w podziemiach pierwszego budynku kościelnego. Choć grób się nie zachował, to pamięć o Heermannie przetrwała. Nazwano jego imieniem organy w kościele, które jednak zostały zniszczone podczas wojny przez stacjonujące w kościele wojna radzieckie. W 1928 r., z okazji 300-lecia parafii luterańskiej w Lesznie, umieszczono we wnętrzu tablicę pamiątkową z fragmentem pieśnie J. Heermanna „O, Panie Boże mój”.
Kościół Krzyża w Lesznie był w opinii pruskiego konserwatora zabytków w Poznaniu, Juliusa Kothe, najcenniejszym kościołem ewangelickim w całym Poznańskiem, odznaczał się także wyjątkową akustyką.