Black Desert Online oyununun hikayesi, dört ana ülke olan Calpheon, Serendia, Balenos ve Media'nın Valencia ile olan etkileşimlerine odaklanır 1.

Valencia, haritanın sağ tarafında bulunan büyük bir ülkedir ve Media, Valencia ile diğer ülkeler arasında yer alır 1. Media, Kara Taş'ın değerini fark ederek, ittifaktan erzak veya silah yerine Kara Taş talep eder 1. Diğer ülkeler, Kara Taş'ın değerini henüz bilmedikleri için Media'ya fazla ve ucuza Kara Taş satarlar 1. 30 yıl süren savaşın ardından, Media, Valencia ile olan ticaretini sürdürerek hazinesini geliştirir 1.

Savaşın ardından, diğer ülkeler Media'nın güçlü bir ülke haline geldiğini görür ve Calpheon, diğer ülkelerin taşlarını çalmaya karar verir 1. Bazı insanlar ise Kara Taş çıkan madenleri kutsal kabul edip yağmalayıcılardan korumaya çalışır 1.

Oyun, bu çatışmaların ortasında kalan kahramanların hikayesini anlatır 1.