Η πρώτη προσπάθεια έγινε στις αρχές του 1901 όταν η ελληνική κυβέρνηση εκτίμησε ότι οι συνθήκες ήταν κατάλληλες για την ίδρυση «Ελληνικής Κοινότητας Ορθοδόξων Κιλκισίου». Έτσι, το Φεβρουάριο αυτής της χρονιάς ο υπουργός Εξωτερικών Άθως Ρωμάνος έστειλε οδηγίες στο Γενικό Πρόξενο Θεσσαλονίκης Ευγένιο Ευγενιάδη για τις δράσεις που έπρεπε να αναληφθούν. Η απόπειρα ίδρυσης ελληνικής κοινότητας στην «Ακρόπολη του βουλγαρισμού», όπως αποκαλούνταν το Κιλκίς, ανακοινώθηκε με τυμπανοκρουσίες από τη εφημερίδα ΕΜΠΡΟΣ του Δημητρίου Καλαποθάκη, αλλά τελικά απέβη άκαρπη.
Η προσπάθεια συνεχίστηκε μετά την έλευση το Σεπτέμβριο του 1903 του νέου αρχιερατικού επιτρόπου Ευγένιου Δόμβρου και πάλι χωρίς αποτέλεσμα. Το 1904 ο πρόξενος Λάμπρος Κορομηλάς προσέγγισε τον Χιλμή Χουσεΐν πασά, Γενικό Επιθεωρητή των ευρωπαϊκών βιλαετίων και απέσπασε την υπόσχεση του να βοηθήσει την ίδρυση ελληνικής κοινότητας, κι αυτή όμως αποδείχθηκε χωρίς αντίκρισμα. Έτσι, το 1906 η Ελληνική Κοινότητα Κιλκισίου σύμφωνα με τον Δ. Φιλιππίδη αριθμούσε 40 οικογένειες, ενώ η βουλγαρική, που είχε ιδρυθεί το 1869, είχε την απόλυτη κυριαρχία στην πόλη μετά την προσχώρηση σε αυτήν της πλειοψηφίας των Ουνιτών.
Μέσα σε αυτό το κλίμα το 1906 ανεγέρθηκε η εκκλησία της «Μεταμορφώσεως του Σωτήρος», η γνωστή μετέπειτα εκκλησία των «Δεκαπέντε Μαρτύρων». Σε έγγραφο της βουλγάρικης ορθόδοξης εκκλησιαστικής κοινότητας Κιλκίς που υπογράφεται στις 18-11-1906 από τον πρόεδρο της Αρχιμανδρίτη Α. Βαρμπάνοφ αναφέρεται ότι η εκκλησία ανεγέρθηκε «με τους συνεχείς εθελοντικούς εράνους του θεοσεβούς και ορθοδόξου πληθυσμού της πόλεως του Κιλκίς και με τους συνεχείς εράνους που έκαναν τα εσνάφια. Η ανέγερση αυτού του ιερού ναού άρχισε στις 25 Αυγούστου και τα θεμέλια τέθηκαν εντός των ορθοδόξων νεκροταφείων που βρίσκονται στην τοποθεσία με την ονομασία «Νέος μαχαλάς».
Οι Στρωμνιτσιώτες μετά την άφιξη τους στο Κιλκίς τον Δεκαπενταύγουστο του 1913 μετονόμασαν τη βουλγάρικη εκκλησία της Μεταμορφώσεως του Σωτήρος, σε εκκλησία των Δεκαπέντε Μαρτύρων, που ήταν και οι πολιούχοι άγιοι της Στρώμνιτσας. Στη γενέτειρά τους υπήρχε εξωκκλήσι των Πεντεκαίδεκα Μαρτύρων, μπροστά από το οποίο υπήρχαν θεμέλια παλαιοχριστιανικής βασιλικής. Στη θέση εκείνη οι Στρωμνιτσιώτες είχαν αποφασίσει να ανεγείρουν ναό, αλλά η επιθυμία τους δεν εκπληρώθηκε καθώς μεσολάβησε ο εκπατρισμός τους.
Μαζί με τους πρόσφυγες, αστούς και αγρότες, ήρθαν και οι ιερείς τους, όπως γράφει ο Αριστείδης Λευκίδης: «Πρώτοι κληρικοί που εγκαταστάθηκαν μαζί με τους πρόσφυγες της Στρώμνιτσας ήταν ο παπά - Μόσχος και ο παπά – Παντζούρης και αργότερα ένας ιερέας από το Γιασίκιοϊ (Ίασμος Ξάνθης). Αργότερα εγκαταστάθηκαν και οι ιερείς παπα - Πέτρος Παπαγιαννάκης από τη Δοϊράνη, παπά Γεώργιος Μπαγανάς από το Καρς και παπά- Ευθύμιος Μυλόπουλος από το Σοχούμ της Ρωσίας».
Οι Στρωμνιτσιώτες μαζί με τα υπάρχοντά τους διέσωσαν και μετέφεραν στη νέα τους πατρίδα, το Κιλκίς, και τα ιερά τους κειμήλια. Ανάμεσα στα κειμήλια που τοποθετήθηκαν στη μετονομασθείσα εκκλησία της Μεταμορφώσεως ξεχώριζαν η μεγάλη εικόνα των Δεκαπέντε Μαρτύρων που είχε φιλοτεχνήσει το 1851 ο αγιογράφος Νικόλαος Χατζημιχαήλ από το Κρούσοβο καθώς και το λείψανο του δεξιού χεριού του ιερομάρτυρα Πέτρου, τοποθετημένο σε αργυρή θήκη.
Η εκκλησία αυτή από το 1913 έως το 1924 λειτούργησε ως Επισκοπικός ναός και έως το 1930 ως Μητροπολιτικός. Τη δημιουργία νέων εικόνων και την ανακαίνιση του τέμπλου ανέλαβε ο αγιογράφος Γρηγόριος, απόφοιτος της Σχολής Καλών Τεχνών της Πετρούπολης. Ο Γρηγόριος ήταν αξιωματικός του τσαρικού στρατού που κατέφυγε στην Ελλάδα μετά την επανάσταση των μπολσεβίκων 1917, παρέμεινε στο Κιλκίς μέχρι το 1940, οπότε έφυγε για την Αθήνα και χάθηκαν τα ίχνη του.
Η περιοχή γύρω από την εκκλησία έλαβε το όνομα της, όπως φαίνεται στην απόφαση 30/1916 του Δημοτικού Συμβουλίου Κιλκίς που αφορά την «επιχωμάτωσιν φρεατίων εν ταις συνοικίαις Αγίου Δημητρίου, Διοικητηρίου και Αγίων Δεκαπέντε Μαρτύρων». Ο δρόμος, επίσης, μπροστά από την εκκλησία, η σημερινή Βενιζέλου, ονομαζόταν κι αυτός Δεκαπέντε Μαρτύρων και μετονομάσθηκε σε Λεωφόρο Νίκης προκαλώντας τις διαμαρτυρίες του συλλόγου Στρωμνιτσιωτών «Η Τιβεριούπολις», που υπέβαλε σχετική ένσταση, η οποία συζητήθηκε στις 28 Δεκεμβρίου 1929.
Στο Ρυμοτομικό Σχέδιο του 1923 ο χώρος της εκκλησίας προς τα δυτικά καταλάμβανε ένα τμήμα του μετέπειτα Γ’ Δημοτικού Σχολείου, ενώ Ανατολικά προβλεπόταν χώρος Γαλλικού νεκροταφείου, όπου είχαν γίνει και ταφές νεκρών στρατιωτών του Α’ Παγκοσμίου πολέμου. Το 1932 ο χώρος διευρύνθηκε καταλαμβάνοντας τμήμα του τότε ποδοσφαιρικού γηπέδου του 13ου Συντάγματος, ενώ το 1936 η εκκλησία ανακαινίσθηκε και διευρύνθηκε και αυτή κατά μερικά μέτρα. Δεύτερη διεύρυνση κατά 4μ προς τα δυτικά, σύμφωνα με τον Αριστείδη Σιδέρη έγινε το 1954-57.
Η μνήμη των Πεντεκαίδεκα Μαρτύρων, πολιούχων της Στρωμνίτσης παρέμενε ζωντανή στους Στρωμνιτσιώτες πρόσφυγες του Κιλκίς και οι εκδηλώσεις τιμητικής λατρείας, με επίκεντρο την εκκλησία των Δεκαπέντε Μαρτύρων, κορυφώνονταν την 28η Νοεμβρίου, ημέρα του Μαρτυρίου τους.
