Pomysł wybudowania kościoła św. Krzyża poza murami miasta (tzw. Jerozolimskiego) wyszedł od zakonu Bożogrobców. Zależało im na zachowaniu tzw. miary jerozolimskiej, czyli odległości odpowiadającej dystansowi między domem Piłata a miejscem ukrzyżowania Jezusa w Jerozolimie. Jako zakon wywodzący się z Ziemi Świętej dobrze znali oni topografię miejsc Męki Pańskiej.
W Nysie punktem odniesienia dla domu Piłata był ratusz stojący na rynku, a miejsce pod budowę kościoła wyznaczono tam, gdzie wcześniej znajdował się drewniany kościółek. To właśnie do niego w średniowieczu odbywały się procesje. W 1633 roku drewnianą świątynię rozebrano, a w krótkim czasie wzniesiono nowy, murowany kościół, konsekrowany 14 kwietnia 1639 roku. Powstał on dzięki ofiarom mieszkańców, a władze miejskie zobowiązały się do jego materialnego utrzymania. Na fasadzie namalowano charakterystyczny podwójny krzyż Bożogrobców.
W wieżyczce kościoła odkryto dokument z 10 października 1678 roku, który potwierdzał, że świątynię zbudowano na pamiątkę Męki Pańskiej, przy zachowaniu rzeczywistej odległości między domem Piłata a Golgotą. Zwyczajem mieszkańców stało się coroczne pielgrzymowanie w Wielki Piątek o godzinie 12.00 z kościoła św. Jakuba do kościoła św. Krzyża.