Över alla andra hus i staden syntesBykyrkan (det vill säga by=stad). Den kallas ibland för Storkyrkan eftersom den var en av Sveriges största kyrkor. Kyrkan var tillägnad S:t Nicholaus, sjöfararnas och köpmännens helgon. Kyrkan byggdes omkring 1200, först som en relativt liten kyrka. Sen utvidgades den omkring sekelskiftet 1300. I slutet av 1300-talet byggdes det till ett antal kapell vid kyrkans långsidor. Till slut blev det sex kapell med altare vid ena långsidan och sju vid den andra. I början av 1400-talet stod kyrkan färdig som en stor femskeppig kyrka. 1430 förklarade kung Erik av Pommern kyrkan som "halvan dom", det vill säga nästan i klass med en domkyrka. Kyrkan var hela 75 meter lång och 38 meter bred. Den var byggd av kalksten med en grundmur av gråsten. Golvet var av tegel. Till kyrkan hörde ett antal präster. De första århundradena har prästerna ofta tyska namn. Den tyska delen av befolkningen hade sannolikt ett stort inflytande vid val av kyrkoherde.
Vid furstebesök i stan var det alltid en festhögmässa i kyrkan. Den största händelsen inträffade när Erik av Pommern Trefaldighetssöndagen 1397, den 17 juni, kröntes till kung över de tre nordiska rikena och 133 adelsmän dubbades till riddare.
En av kyrkans mest kända präster var Claus (Nicolaus) Köning, en Kalmarpojke som sedemera blev biskop i Linköping, kallad biskop Nils. Nils bodde även efter att han blivit biskop kvar i Kalmar.
I staden fanns en mindre kyrka, Birgittakyrkan, omtalad för första gången på 1440-talet. Kanske höll man till i ett hus som ursprungligen tillhört Birgittasystrarna i Vadstena.