Согласно информации Яна Длугоша, первый каменный костёл в романском стиле был основан в 1221—1222 годах епископом Иво Одровонжем на месте прежнего деревянного храма. Вскоре, однако, костёл был уничтожен в результате татарских набегов.

В 1290—1300 годах, частично на прежнем фундаменте, был построен раннеготический зальный храм, освящённый около 1320—1321 годов. Между тем, строительные работы продолжались.

В 1355—1365 годах на средства Миколая Вежинка, краковского мещанина и сандомирского стольника, выстроен современный пресвитерий.

В 1392—1397 годах мастер Миколай Вернер выполнял заказ на улучшение освещения костёла. С этой целью были понижены стены боковых нефов, а в главном были добавлены большие оконные проёмы. Таким образом костёл из зального храма превратился в базилику.

В результате землетрясения 1443 (или 1442) года частично был повреждён свод храма.

В первой половине XV века были достроены боковые часовни. Большая часть из них была результатом работы мастера Франтишека Вехоня из краковского предместья Клепажа. В это же время была надстроена северная башня, исполнявшая тогда функции городской сторожевой. В 1478 году плотник Матиас Херингкан увенчал башню шлемовидной главой. На ней в 1666 году установлена позолоченная корона.

В конце XV века Мариацкий костел обрёл одно из главных своих украшений — скульптурный шедевр поздней готики — Большой алтарь — творение Вита Ствоша.

В XVIII веке, по заказу архипресвитера Яцека Августа Лопацкого, внутреннее убранство костёла приобрело позднебарочный характер. Автором этих работ был архитектор Франческо Плациди. Было сменено 26 алтарей, а также другое убранство, лавы, образы, а стены были украшены полихромией кисти Анджея Радваньского. С тех же времен происходит позднебарочная крухта.

В начале XIX века, в рамках благоустройства города, было ликвидировано прикостельное кладбище, на месте которого сейчас находится Мариацкая площадь.

В 1887—1891 годах под руководством Тадеуша Стрыенского убранству костёла был придан неоготический облик. В храме появилась новая полихромия — на этот раз по проекту и в исполнении Яна Матейко, которому помогали Станислав Выспяньский и Юзеф Мехоффер — авторы витражей в пресвитерии и над главными органами.

8 марта 1973 года церковь была внесена в реестр памятников Малопольского воеводства.

С начала 1990-х гг. проводились комплексные реставрационные работы, в результате которых костёл был очищен от загрязнений, которые оседали на его стенах на протяжении всего XX века, скрывая изумительную полихромию. Костёлу был возвращен его первоначальный блеск. Завершающим этапом работ была реставрация крыши костёла, оконченная в 2003 году.

18 апреля 2010 года в Мариацком костёле проходила церемония прощания с президентом Польши Лехом Качиньским и его супругой Марией, погибшими в авиакатастрофе под Смоленском 10 апреля 2010 года. После президентская чета была похоронена в одной из крипт Вавельского собора.