Již v románské době stával na tomto místě kostelík zasvěcený svatému Jiří. V roce 1371 byl místo něj postaven gotický kostel. Zakladatelem kostela byl Petr ze Šternberka. Téhož roku přivedl Albert II. do Šternberka augustiniány lateránské kongregace, kteří začali budovat u kostela klášter.
Gotický kostel i klášter velmi utrpěl v husitských bojích roku 1430. Později kostel dvakrát vyhořel, byl proto roku 1775 zbořen a započalo se se stavbou nynějšího kostela. Nový chrám byl stavebně dokončen v roce 1783 a probošt Ondřej Tempes jej 17.11. téhož roku posvětil. Kostel byl postaven ve slohu klasicistickém. Stavitelem byl brněnský architekt
František Antonín Grimm, přední osobnost soudobé architektonické tvorby v moravském prostředí. V 18. století císař Josef II. zrušil augustiniány ve Šternberku a kostel se stává farním.
Ve šternberské kapli je obnovena vzácná stropní malba
Kryštofa Handkeho, zachycující historii Šternberka. Chrámový prostor je jednolodní, mohutná klenba je vyzdobena nástropní malbou od moravského malíře
Antonína Sebastiniho Šebesty z Prostějova. Kostel je 65 m dlouhý, výška chrámové lodi je 30 m. Věže jsou vysoké 60 m. Z gotické stavby se zachovala část
křížové chodby, která spojuje kostel s klášterem.
Vzácnou památkou šternberského kostela je tzv.
Šternberská madona, kamenná socha z konce 14. st., patřící do okruhu krásných madon. Gotická Šternberská madona je aktuálně zapůjčena a vystavena v
Arcidiecézním muzeu v Olomouci.