Išlikę daug pasakojimų, kodėl būtent šioje vietoje pastatyta Katedra. Legenda sako, kad kartą į Šiaulius atėjo didžiulis jautis ir atsigulęs pailsėti užmigo amžinu miegu. Laikui bėgant, vėjas apnešė jį žemėmis ir taip susidarė aukštumėlė, ant kurios dabar stovi Šv. Apaštalų Petro ir Pauliaus katedra.
Pirmąją medinę bažnyčią Šiauliuose 1445 m. pastatė Žemaičių seniūnas M. Kęsgaila. Ji turėjo nuolatinį kunigą. 1617–1626 m. pastatyta nauja mūrinė bažnyčia. Zigmantas Vaza jos išlaikymui 1617 m. skyrė 72 valakus žemės. 1625 m. ant bažnyčios sienos pritvirtintas saulės laikrodis. 1655 m. bažnyčia apdegė. Klebonui 1676 m. nurodyta ją restauruoti.