Mustasaaren kaupunki perustettiin Mustasaaren emäseurakunnan alueelle kuninkaan käskykirjeellä 2.10.1606 ja se sai privilegionsa Vaasan kaupingin nimellä 1611. Kaupungin perustamisen jälkeen jakamatonta emäseurakuntaa alettiin kutsumaan Vaasan ja Mustasaaren seurakunnaksi. Kaupunkiin liitettiin useita tiloja emäseurakunnasta sekä Isonkyrön ja Vähänkyrön seurakunnista 1651. Seurakunnan vanha kirkko, joka oli koko emäseurakunnan yhteinen ja Marian nimikko, rakennettiin 1616. Kirkko pidennettiin 1653-1669, rakennettiin ristikirkoksi 1750 ja paloi kaupungin mukana 3.8.1852. Kaupunki siirrettiin lähemmäksi satamaa ja kaupunki sai edesmenneen Venäjän keisari Nikolai I:n mukaan nimen Nikolainkaupunki keisarin käskykirjeellä 3.11.1862, jolloin myös Klemetsön eli Klemettilän alue liitettiin kuuluvaksi kaupunkiin. Kaupunki erotettiin Mustasaaresta itsenäiseksi kirkkoherrakunnaksi keisarin käskykirjeellä 30.3.1867. Kaupunki jaettiin kielellisellä perusteella Vaasan suomalaiseen ja ruotsalaiseen seurakuntaan 1927.
Muut nimet
Vasa, Nikolainkaupunki, Nikolaistad, Vaasa ja Nikolainkaupunki, Vasa och Nikolaistad
Papisto
Kaupungin äänten laskemisesta papiston vaaleissa keisarillisen senaatin käskykirjeet 1.9.1830 ja 3.5.1861. Mustasaaren emäseurakunnan papiston palkasta kaupungista 17.1.1861 ja 7.8.1861. Nikolainkaupungin papiston palkasta keisarillisen senaatin päätös 30.3.1867. Komministerin palkasta keisarin käskykirjeet 16.1.1873 ja 3.6.1880. Komministerin palkasta tehtiin suostumus 12.4.1875. Kirkollisten maksujen maksamisen perusteista keisarillisen senaatin päätös 26.1.1876. Sporttelitaksasta keisarillisen senaatin päätös 27.6.1884. Päätöksestä toisen komministerin asettamisesta kaupunkiin ja komministerin 3 600 markan palkasta tuomikapitulin vahvistus 16.5.1896 ja keisarillisen senaatin päätös 21.12.1897.
Seurakuntaan perustettiin papiston apulaisen virka tuomiokapitulin päätöksellä 20.6.1907, jolloin virkaan asetettavan papin virkapaikaksi tuli Palosaaren eli Brändön esikaupunki, jonne seurakunta suunnitteli rukoushuoneen rakentamista kivestä, ja rukoushuoneen yhteyteen myös asuntoa esikaupunkipapille.
Kirkkoherrat
1874–1876 Karl Vilhelm Vegelius
1879–1894 Abel Nyholm
1895–1918 Joel August Heikel
1920–1927 Lauri Johannes Roschier, siirrettiin Vaasan suomalaisen seurakunnan kirkkoherraksi
Kappalaiset
1862–1874 Karl Vilhelm Vegelius, virka muutettiin komministerin viraksi
1. komministerit
1874–1878 Johannes Bäck
1879–1895 Joel August Heikel
1895–1905 Karl Konstantin Olander
1906–1927 Karl Oskar Ahlström, siirrettiin Vaasan ruotsalaisen seurakunnan kirkkoherraksi
2. komministerit
1899–1927 Johan Erik Kovero, siirretiin Vaasan ruotsalaisen seurakunnan komministeriksi
Ylimääräiset papit
1873–1874 Johannes Bäck, vt. kirkkoherra, vt. komministeri
1878–1879 Joel August Heikel, vt. kirkkoherra
1885 Arnold Melker Berger, vt. kirkkoherra
1894–1895 Peter Cederberg, välisaarnaaja
1896–1899 Johan Erik Kovero, kirkkoherran apulainen, vt. komministeri
1902 Johan Albert Lundelin, kirkkoherran apulainen
1902–1903 Frans Emil Lehto, papiston apulainen
1902 Juho Vihtori Korpi, papiston apulainen
1904 Alfred Teodor Appelberg, vt. 1. komministeri
1905–1906 Kaarlo Väinö Sivenius, vt. 1. komministeri, vt. kirkkoherra
1907–1909 August Bruno Forsberg, papiston apulainen
1909– Lauri Rikala, kirkkoherran apulainen
1909–1910 Kauko Väinö Kustavi Vahervuori, papiston apulainen
1910–1912 Lauri Rikala
1913–1916 Julius Johannes Björklund
1916–1918 Leo Richard Böök
1918–1919 Lennart Albert Heljas (Helenius)
1919–1922 Olav Daniel Schalin
1922–1927 Jalo Johannes Jalkanen
Arkisto
Vaasan seurakunnan rippikirjat alkavat vuodesta 1761, tilikirjat vuodesta 1828 ja historiakirjat vuodesta 1803. Seurakunnan vanhinta arkistoa säilytetään Kansallisarkisto Vaasassa ja aineistokokonaisuus kattaa vuodet 1564–1953.
Kansallisarkisto on digitoinut Vaasan seurakunnan vanhimmat kirkonkirjat noin 1860-luvulle saakka ja aineisto on vapaasti tutkittavissa Astia-palvelussa. Suomen Sukuhistoriallinen yhdistys (SSHY) on digitoinut seurakunnan nuorempia kirkonkirjoja. Alle 125 vuotta vanhojen aineistojen tutkiminen vaatii kirjautumisen yhdistyksen jäsensivuille.