ako je vrijeme utemeljenja kreševskog samostana nepoznato, zna se da je postojao već u doba bosanskog srednjovjekovlja, a najvjerojatnije je prvotno podignut već koncem XIV. stoljeća. Već tada je, kao i drugdje, uz samostan postojala i crkva izgrađena u gotičkom stilu, a uz nju je, vjerojatno već u 15. stoljeću, i kamena kapela Sv. Marije

Ne zna se sudbina crkve i samostana u teškim vremenima pada Bosne pod osmanlijsku čizmu. Po svemu sudeći u Kreševu nije bilo većih borbi, pa su samostan i crkva uspjeli opstati, no, šezdesetak godina kasnije, 1521. ili 1524. godine, srušeni su. Iako je kod turskih vlasti bilo jako teško dobiti dozvole za gradnju, u tome se nekako uspjelo, pa su crkva i samostan ponovno podignuti.

Novi teški udes dogodio se na Uskrs 1765. godine, dvije godine nakon temeljite obnove, kada su samostan i crkva potpuno izgorjeli. U požaru je izgorjela i sva imovina, uključujući i stare matične knjige, knjižnicu i arhiv, misno posuđe i sve ostalo što se u samostanu i crkvi zateklo. Svaka nova gradnja u to doba je bila povezana s brojnim poteškoćama, budući da se svaki put morala tražiti nova dozvola, koja se skupo plaćala, a novogradnja nikad nije smjela biti veća od prethodne, niti od čvrstog materijala. Tako su do dobivanja dozvole za obnovu, uz mnoge probleme i troškove, prošle čak dvije godine, pa je potom sve građeno ispočetka. Ugradnji su sudjelovali klesari, tesari i zidari od Mostara, Fojnice, Kreševa, Travnika, Žepča, Tuzle i Tešnja, njih više od stotinu, među kojima i mnogi pravoslavci. Brojni su župljani sudjelovali kao pomoćni radnici. Radovi su trajali od 27. lipnja do 4. studenoga 1767. godine.

Za nekoliko desetljeća zgrade su već bile trošne, pa se moralo pomišljati na popravke. Kako su za to bili potrebni veliki izdaci, a samostan iscrpljen turskim nametima, kreševski su franjevci bili prisiljeni ići u Italiju i tamo skupljati milodare u tu svrhu. Godine 1822. izmijenjen je krov na samostanskoj zgradi, a do 1827. dovršena je obnova i samostana i crkve. Početkom 19. stoljeća (1804.) nabavljene su orgulje, uz fojničke tada jedine u Bosni i Hercegovini, ali one nisu sačuvane.

Godine 1853. započeta je gradnja nove trobrodne crkve uneoromaničkom stilu. Gradnja je trajala do 1870. godine, a dvije godine kasnije dozidan je i zvonik. U novoj crkvi nalazilo se 14 vitkih stupova, koji su nosili polukružne lukove i drveni bačvasti svod. Devet godina kasnije crkva je pojačana potpornim stupovima, a 1883. godine su pobočne lađe pokrivene limom, dok je na glavnoj lađi i dalje ostao drveni krov. Godine 1887. u crkvu je postavljen Gospin oltar, izveden u Grazu, po nacrtu arhitekta Josipa Vancaša. Oltarsku sliku Bezgrešno začeće iste je godine naslikao Alexander Seitz.

Godine 1924. obnovljena je i ponutrica crkve, sagrađene prema nacrtu Karla Paržika. Postavljeni su i novi oltari, a jedan od njih, izveden od betona, bio je i uzrokom tonjenja svetišta, pa je cijela građevina 1963. godine srušena, te je potom, po nacrtu Antuna Karavanića, podignuta sadašnja crkva. Prvotni projekt dijelom su modificirali arhitekt T. Ćuk i statičar S. Malkin. Crkva je svečano  blagoslovljena na blagdan zaštitnice, svete Katarine, 25. studenog 1965. godine, a gradnja je završena 1970. godine.

Na pročelju crkve Ivo Dulčić je 1974. godine izveo pet tema u mozaiku: Sv. Katarina, Sv. Leopold, Sv. Nikola Tavelić, Sv. Franjo Asiški i Gospino krunjenje. Po Dulčićevu nacrtu je 1981. godine izveden veliki vitrail, osim lika Djevice Marije, koji je izveo Đuro Pulitika. U crkvi se nalazi Križni put Đure Sedera.  

Orgulje od 25 registara izgradila je tvrtka M. Heferer 1957. god. Nakon izgradnje nove crkve one su preuređene i postavljene u prezbiteriju (1970.).

Samostan i crkva posjeduju i dvadesetak vrlo vrijednih umjetničkih slika, većinom od nepoznatih venecijanskih majstora iz XVII. stoljeća: Sv. Jeronim, Sv. Ana, Joakim i Marija, Krunjenje Marijino sa Sv. Rokom i Ilijom, Posljednja večera, Raspeće Kristovo, Madona s Kristom, Sv. Obitelj s Ivanom Krstiteljem (18. st.), Sveci Franjevačkog reda (17.-18. st.). Iz 17. stoljeća je i Madona s Kristom nepoznatog baroknog majstora, te Posljednji sud slikara Baldassare D'Anna. Tu su i mnoge slike iz kasnijih razdoblja. Najznakovitija je slika nepoznatog autora Bosanska kraljica sa sv. Franjom daruje kreševski samostan Majci Božjoj, djelo nepoznatog autora iz 1750. godine.Iznimno vrijednim smatra se kip Sv. Katarine (bojeno drvo) nepoznatog talijanskog majstora s konca 15. ili početka 16. stoljeća.

Od rijetkih djela domaćih majstora u zbirci je slikaStigmatizacija Sv. Franje fra Mihe Čuića, te Žalosna Gospa od kreševskog franjevca fra Petrušića (obje iz druge polovice 18. stoljeća). Od modernih umjetničkih djela samostan posjeduje brončano Raspelo Ivana Meštrovića, Posljednju večeru (ulje na platnu) Đure Sedera i druge.

Godine 1996. obnovljen je crkveni krov, a 2008. godine su umjesto starih providnih prozora na bočnim i zadnjoj strani crkve postavljeni vitraji.