Composé de membres issus de différentes formations et créé en 1999 à l'initiative de Thomas, Fabrice, Khrees, Michel, Olivier et Nicolas Etienne, le groupe sort rapidement un 1er album éponyme sous le nom de Aldebaran. Peu après la sortie de ce 1er opus autoproduit et distribué localement, le groupe se sépare de son chanteur. Commence alors une longue série d'auditions qui durera jusqu'en...2002 !!!!!!!! C'est alors que Nicolas David, chanteur et ami de longue date de Thomas, quitte sa Normandie natale pour s'installer à Toulouse.

Dans l'intervalle, un nouveau bassiste, Marc Johnson, rejoint le combo.

Le groupe, rebaptisé Veda, donne son 1er concert en avril et rentre en studio en Mai pour enregistrer une démo 5 titres. Elle est acceuillie avec enthousiasme par certains magazines nationaux comme Hard Rock mag et Guitarist magazine et leur permet d'effectuer plusieurs passages sur des radios locales (Delirium city sur FMR, Metal Nemesis sur radio Mon Pais et Metalstorm sur Spin FM). En novembre 2002, Veda se voit offrir l'honneur d'ouvrir pour Bumblefoot sur 2 dates de sa tournée française . A cette occasion, le groupe bénéficie d'un passage TV sur le décrochage régional de M6 Toulouse.

Après avoir fait la 1ère partie de Taboo Voodoo ( Cyril Achard, Mike Terrana...), l'année 2003 marquera un tournant décisif pour le groupe. Marc et Khrees décident de quittter le groupe alors que le combo s'apprête à enregistrer son 1er album . Le groupe ne désarme pas et retrouve rapidement un bassiste , Aurélien et un batteur, Sébastien Albert (qui nous quittera après l'enregistrement de l'album).

L'album est enregistré en 2004 pour une sortie prévue en 2005 .