Вихованець клубу «Динамо» (Загреб). 26 лютого 2011 року він дебютував у Першій хорватській лізі, вийшовши в основному складі в гостьовому поєдинку проти «Карловаца»[1]. На 12-й хвилині матчу Шитум забив свій перший гол на вищому рівні.
На початку 2012 року Маріо Шитум був відданий в оренду «Локомотиві», де провів 2,5 сезони, після чого влітку 2014 році відразу був відданий в оренду клубу італійської Серії B «Спеції», де провів ще два роки.
Сезон 2016/17 Маріо відіграв за «Динамо», вигравши з клубом Кубок Хорватії, а влітку 2017 року на правах оренди перейшов до польського «Леха»[2]. Тренерським штабом нового клубу також розглядався як гравець «основи». З 2018 року знову став виступати за рідне «Динамо» (Загреб), вигравши 2019 року з клубом чемпіонат та суперкубок Хорватії. Станом на 23 жовтня 2019 року відіграв за «динамівців» 54 матчів в національному чемпіонаті.
.svg){kind=small}
