Nikt do końca nie wie, kiedy tak naprawdę powstał DENEB. Mniej więcej w 95/96 roku dwóch gitarzystów - Tomek Sulka oraz Grzegorz Skiba postanowiło połączyć swoje siły.

Przez zespół przewijali się najróżniejsi ludzie, co nie pozostawało bez wpływu na rodzaj wykonywanej muzyki. Około roku 1998 zaczęły powstawać pierwsze, reprezentatywne dla obecnego wizerunku DENEB utwory. Rok później do Tomka i Grzegorza grających wówczas z perkusista Grzegorzem Kuchalskim doszedł basista Remigiusz "Rembas" Wojcik oraz wokalista Andrzej "Muflon" Kieś (obaj z zespołu IGOR, który wkrótce zakończył działalność). Mając skompletowany cały skład, T. Sulka szybko podjął decyzję o nagraniu pierwszego dema, właśnie wtedy pierwszy raz została użyta nazwa "DENEB". Drugim wokalistą został Daniel "Pieczara" Perzyna (perkusista IGORa). Od tego czasu charakterystyczną dla DENEB cechą było dysponowanie dwoma rodzajami wokalu: jednego śpiewającego w konwencji death, oraz drugiego typowego dla black metalu. Debiutancki materiał "Principia Chaotica" został zarejestrowany w rybnickim studiu "Rondo" w czerwcu 1999. Jako, że zespół nie posiadał żadnych kontaktów, ani tym bardziej doświadczenia w kwestii promocji, demo przeszło bez większego echa. Jedynym osiągnięciem było wystąpienie w audycji Andrzeja Modrzyka - "Metal Hammer Show" w radiu "Flash". Niedługo po nagraniu pierwszego dema zespół opuszcza G. Kuchalski, jego miejsce zajmuje Pieczara zwalniając tym samym posadę blackowego wokalisty. W to miejsce przychodzi Wojciech "Wojtas" Konkol (którego kapela - DEBRIS - własnie dokonczyła żywota). Rembas także decyduje się opuścić szeregi DENEB, jego nastepcą zostaje Szymon "Szczupły" Kufa. W takim składzie zespół zagrał swój pierwszy w karierze koncert, w czerwcu 2001r. supportując m.in. VADER oraz SCEPTIC. W listopadzie 2001 roku nadchodzi czas na nagranie kolejnego dema. Do tego celu zostało wybrane leszczyńskie studio "Audio Art". Promocją materiału nazwanego "Diasparagmos" zajął się Mirosław Górka z rybnickiego "Rise For Victory'zine", dzięki czemu zaczęły pojawiać się recenzje w prasie undergroundowej. DENEB był także gościem Agaresa w audycji "Nemezis" w radiu "Park". Po zagraniu kilku lokalnych koncertów zespół opuszcza Wojtas, który postanawia całkowicie poświęcić się swojej nowej kapeli - MOULDED FLESH. Jego miejsce szybko zajmuje Krzysztof "Popi" Popczyk. Po kolejnych koncertach, pod koniec 2002r. z zespołem żegna się jeden z jego założycieli G. Skiba oraz z powodów "rodzinnych" perkusista Pieczara. Bas na gitarę zamienia Szczupły, który w gruncie rzeczy jest gitarzystą, a na basie grał z konieczności, 4-stunowca chwyta Rafal Polnik (ex-MOULDED FLESH), natomiast za gary siada Krzysztof "leon" Lenard (bębniący także w PRO-CREATION).

Po kilku miesiącach grania intensywnych prób Deneb decyduje się na przedstawienie nowych kompozycji na kilku koncertach. Nowe utwory zespołu spotykają się z pozytywnymi opiniami słuchaczy. We wrześniu 2003 z zespołu odchodzi Rafał, zespół na kilka miesięcy staje w miejscu nie potrafiąc znaleźć nowego basisty i nieoficjalnie przestaje istnieć. Po dwóch miesiącach znów mają miejsce regularne próby i szlifowanie materiału (basisty wciąż brak). Nadchodzi marzec 2004 roku i moment przełomowy - w nasze szeregi powraca Rafał i zespół podejmuje szybką decyzję rejestracji materiału. Proces nagrywania rozpoczyna się w maju i trwa aż do września, w międzyczasie z powodów czysto osobistych zespół opuszcza Popi. Obróbką gotowego materiału decydują się zająć chłopaki z Kraszer Inc. Lecz efekt końcowy nie jest w pełni zadowalający (głównie za sprawą słabej jakości nagrań partii poszczególnych instrumentów). Zespół postanawia powtórzyć sesję nagraniową. Na początku października odchodzi Muflon i zespół zostaje bez głównego wokalisty. Jego partie na płytę zgadza się nagrać Wojtas z MOULDED FLESH. W połowie grudnia nagrania ruszają pełną parą by zakończyć się w pierwszych dniach lutego 2005.

09.02.2005 - Końcowe mixy i mastering zakończone, płyta "A Path Without Destination" jest w 1000% gotowa.

Pod koniec czerwca 2005r. DENEB rozpoczyna regularne próby z nowym wokalistą. Z dniem 20.08.2005r. Szymon "Sajmon" Skatuła, znany wcześniej głównie z występów w rydułtowskim Katharsis zostaje oficjalnym członkiem zespołu.