Šv. Jono bažnyčia Klaipėdoje minima bemaž nuo miesto įkūrimo XIII amžiaus viduryje. Klaipėdos Šv. Jono parapija savo istorijos atskaitos tašku laiko 1258-uosius metus. Iš šio laikotarpio istorikams žinomi vos keli XIII amžiaus dokumentai, kuriuose kalbama apie Šv. Jono bažnyčią, o archeologams jos aptikti dar nepavyko.
Iš šalia pilies gyvavusio viduramžių miesto XVI amžiuje bažnyčia dėl gynybinių įtvirtinimų plėtros kartu su miestu buvo perkelta į dabartinį senamiestį. Seniausi parapijos maldos namai, kurių vietą šiandien įmanoma tiksliai nustatyti, tarp 1562 ir 1571 metų iškilo prie Dangės upės, dabartinės Turgaus gatvės gale (sovietmečiu virš bažnyčios pamatų čia stovėjo saldainių fabrikas). Tačiau XVIII amžiuje plečiant miesto bastionus, bažnyčiai vėl teko ieškoti naujos vietos. Iš čia į greta esantį didelį sklypą (Turgaus g. 24) parapija persikėlė 1706 metais. Šioje vietoje ir ruošiamasi atstatyti Šv. Jono bažnyčią.
Nors nuo viduramžių iki naujausių laikų bažnyčia vadinta įvairiai, keitėsi jos išvaizda ir vieta, turima duomenų, kad parapija veikė nepertraukiamai nuo nuo XVI a., o bažnyčia buvo atstatoma. Nuo XVI amžiaus vidurio iki XIX amžiaus vidurio ji buvo vadinama Vokiečių bažnyčia, Liuteronų bažnyčia, Miesto bažnyčia. Prieš paskutinįsyk keičiant pavadinimą 1857 metais parapijos pavadinimas buvo Deutsch lutherische Gemeinde, o bažnyčia vadinta Deutsch lutherische Kirche. Parapija ir bažnyčia Šv. Jono vardu imta vadinti tik 1857 metais.
Vokiečių bažnyčia Klaipėdoje turėjo aukštesnį nei įprasta parapinė bažnyčia statusą. Vėliausiai nuo 1591 metų bažnyčia veikė kaip vyskupinė Klaipėdos valsčiui, turėjusi inspektuoti kitas valsčiaus bažnyčias.