Fondata nel 1993, in pieno conflitto dei Balcani, la squadra ha partecipato al suo primo campionato di massima serie nella stagione 1994-1995, quando ancora il torneo era suddiviso in gironi. L'Olimpic ottenne un buon terzo posto nel suo girone, sfiorando la qualificazione alla fase finale per l'assegnazione del titolo. Nella stagione successiva, la prima a girone unico, il 15º posto su 16 squadre significò retrocessione, cui seguì rapidamente anche una discesa nelle serie inferiori. L'assenza dal calcio d'élite durò fino alla stagione 2007-2008, quando l'Olimpic ottenne il ritorno in Prva Liga FBiH (uno dei due gironi in cui è suddivisa la seconda serie nazionale); da neopromossa, nel 2008-2009 vinse il suo campionato ed ottenne così una seconda promozione consecutiva che le permise di risalire in massima serie.