Клуб основан 26 апреля 1911 года. В 1912 году «Граджянски» стал бронзовым призёром первого (и единственного на долгие годы) чемпионата Хорватии. С 1923 по 1940 годы клуб выступал в чемпионате Королевства Югославии, и пять раз, в сезонах 1923, 1926, 1928, 1936/37 и 1939/40 становился чемпионом Югославии, кроме того ещё дважды был вице-чемпионом, тем самым являясь вторым по титулованности клубом Югославии довоенного периода. «Граджянски» трижды представлял Югославию в Кубке Митропы, в 1928, 1937 и 1940 годах, но лишь раз ему удалось пройти дальше первого раунда. Во время второй мировой войны «Граджянски» выступал в чемпионате Хорватии, и стал чемпионом Хорватии в сезоне 1943 года. После второй мировой войны клуб, как и его основные соперники клубы «Конкордия» и ХАШК, был распущен, а на основе этих клубов был создан клуб «Динамо».
В эти годы для клубных команд государств, дружественных странам Оси, был организован так называемый «Европейский футбольный Кубок». В 1944 году «Граджански» играл в его финале, в котором проиграл венгерскому «Надьваради» (ныне ФК «Бихор-Орадя») со счётом 0:4. «Граджански» пользовался расположением фактического хорватского правителя Анте Павелича, а некоторые футболисты клуба, например Иван Хитрец и Звонимир Цимерманчич, были активными пособниками режима.