Милош Шестич народився у місті Лакташі в сучасній Боснії і Герцеговині, в ранньому віці перебрався з батьками до Воєводини. Розпочав грати у футбол у команді «Єдинство» з міста Стара Пазова, а з 1974 рокустав гравцем команди «Црвена Звезда» з Белграда. У найтитулованішій команді тогочасної Югославії Шестич провів одинадцять сезонів, зігравши в складі команди 216 матчів першості, відзначившись у яких 44 забитими м'ячами. У складі команди став чотириразовим чемпіоном Югославії та володарем Кубка Югославії.
У 1985 році Милош Шестич отримав дозвіл на виступи за кордоном, після чого він став гравцем грецької команди «Олімпіакос» з Пірея, у складі якого в сезоні 1986—1987 років став чемпіоном Греції. У 1987 році повернувся до Югославії, та став гравцем клубу «Воєводина», у складі якого у сезоні 1988—1989 років знову став чемпіоном Югославії. З 1989 до 1991 року Милош Шестич грав у складі югославських команд «Земун» та ОФК (Белград), після чого завершив виступи на футбольних полях.