Fondata nel 1913 come TSD Reka Tiča[2][3], nella sua storia il club ha vinto il campionato bulgaro per quattro volte[4][5] e in tre circostanze si è classificato terzo, anche se il Vladislav vinse il campionato bulgaro in tre occasioni e il Tiča in una. Nella stagione 2014-2015 il club, battendo in finale il Levski Sofia, si è aggiudicato la Coppa di Bulgaria, competizione in cui conta anche due finali perse.
il 3 marzo 1913 viene fondata a Varna l'associazione sportiva Galata, più tardi rinominata Reka Tiča. Qualche anno più tardi la squadra si unisce allo Sportist, fino da essere rinominato Sports Club Tiča, e a scegliere come colori sociali il rosso e il bianco. Il club ottiene due secondi posto in campionato a metà degli anni trenta, fino alla vittoria nella stagione 1937-1938.
Il 3 aprile 1916 viene fondato il Vladislav Varna, inizialmente chiamato Sport Club Napred, avente come colori sociali il verde e il bianco. La squadra vince i primi due campionati nazionali nel 1925 e nel 1926. Dopo due secondi posti torna alla vittoria nel 1934. Successivamente conquista altri due secondi posto.
Il club è fondato nel 1945 come TV-45 dalla fusione di FC Vladislav e SK Tiča, nome successivamente mutato in TVP-45 dopo l'ingresso del Primorec nell'unione. Nei primi tre campionati a cui partecipa, svolti nel formato di coppa, viene eliminato nei quarti di finale. Successivamente, in seguito alla riorganizzazione del campionato nazionale, il club disputa il campionato di seconda divisione fino al 1951, quando è nuovamente promosso: nella stagione 1952 si classifica settimo in massima divisione, mentre la stagione successiva ottiene un buon terzo posto. Retrocede in seconda divisione al termine del campionato 1955, lo stesso accade nel campionato 1958-1959, ma in entrambi i casi è subito promosso. Nel 1959 il club si fonde con il Černo More, club di seconda divisione, assumendo l'attuale denominazione.
Il Černo More trascorre tutti gli anni sessanta e buona parte degli anni settanta in prima divisione, ottenendo come massimo risultato il quarto posto conquistato ottenuto nel campionato 1968-1969, e venendo retrocesso solo al termine della stagione 1975-1976. La riconquista della promozione è anche in questo caso immediata. La squadra rimane nel campionato maggiore fino alla metà degli anni ottanta. Gli anni novanta non sono un buon decennio per il club, che torna in prima divisione solo all'inizio degli anni duemila.
Nel 2006 il Černo More giunge per la prima volta in finale di Coppa di Bulgaria, nella quale viene sconfitto per 3-1 dal CSKA Sofia. Nel luglio 2007, dopo aver eliminato il Makedonija Gjorče Petrov, è estromesso dalla Sampdoria dalla Coppa Intertoto con un doppio 1-0. Per la formazione bulgara, allenata da Nikola Spasov, si tratta della prima partecipazione alle coppe europee: prima di allora il Černo More aveva disputato soltanto l'edizione 1982 della Coppa Piano Karl Rappan. Al termine della stessa stagione il club disputa per la seconda volta la finale della coppa nazionale, ma è sconfitto per 1-0 dal Liteks Loveč. Nella stagione seguente la squadra disputa invece la Coppa UEFA, dalla quale è eliminata al terzo turno dallo Stoccarda. Quella stagione si conclude con il terzo posto in campionato: per questo motivo il Černo More Varna partecipa all'Europa League 2009-2010, manifestazione in cui viene eliminata al terzo turno preliminare dal PSV.
Nel 2014-2015 la squadra vince il suo primo trofeo nazionale, aggiudicandosi la Coppa di Bulgaria in finale contro il Levski Sofia dopo aver rimontato l'iniziale svantaggio ed essersi imposta per 2-1.