Malgré les contraintes du temps et des intempéries, il demeure debout. Edifié sur les ruines du palais de l'Etoile, le fort Bordj Moussa a été construit par les Espagnols, et plus précisément par Ferdinand de Navarro, (seul document retrouvé : plan de masse réalisé en 1539). Il servira de château impérial sous le règne de Charles Quint (l'Espagnol qui a régné au 16e siècle). Le fort est un chef-d'oeuvre d'architecture, et malgré les contraintes du temps, et des intempéries, il tient encore debout sur ses piliers. A l'époque espagnole, il se constituait de trois grandes salles; deux salles latérales, une terrasse centrale, et deux autres petites, formant les tours de contrôle. Les murs ont plus de deux mètres d'épaisseur. Le côté Nord du fort en forme de «V» servant à cerner l'ennemi. En 1555, Salah Raïs Pacha ordonnera à l'Espagnol Alfonso Di Peralta, de quitter les lieux et Béjaïa, après sa défaite face aux Turcs. Ces derniers, occupèrent le fort, et lui donnèrent le nom de Bordj-Moussa. Pour revenir à l'origine de ce nom, revenons à l'époque où les Espagnols occupaient encore le fort, ce dernier, et sous l'égide des Turcs sera assiégé par les autochtones qui voulurent s'en emparer. Hélas, la bataille sera rude, et sept valeureux guerriers (R'djel Essabaâ) prirent l'initiative de se sacrifier en s'introduisant dans l'enceinte du fort, où ils furent exécutés tous les sept par les soldats espagnols. Le premier des sept combattants portait le prénom de Moussa, d'où dérive donc le nom de Bordj Moussa attribué par les Turcs à ce fort en reconnaissance au premier homme qui a osé s'aventurer dans le camp ennemi. Les habitants de la ville firent du courage des sept hommes une légende. La légende de R'djel Essabaâ. En 1833, les Français ayant envahi Béjaïa s'emparèrent de Bordj-Moussa, et le dénommèrent Fort-Barral en l'honneur du général Barral, qui succombera à ses blessures tout près de ce fort à l'hôpital de Béjaïa. Il sera enterré à l'intérieur du Fort, avant d'être rapatrié en France. A l'époque française, le fort connaîtra plusieurs transformations. La grande salle sera divisée latéralement en deux pour former un rez-de-chaussée et un premier étage (l'administration). Un carré sera aussi pratiqué dans le plafond pour permettre le passage des monte-charges. Des cellules seront aussi construites pour enfermer les détenus. Après l'indépendance de 1962 à 1964, Bordj-Moussa sera occupé par l'ALN, puis sera livré à lui-même jusqu'en 1987, quand il subira des travaux de réaménagement, et abritera le musée de Béjaïa, dès le 1er novembre 1989. Ce musée a été transféré de ses anciens locaux situés sous la terrasse de la place Gueydon, et qui sont actuellement le siège de Radio-Soummam. Ce musée construit en 1902, par un certain J.Cazaubon a été classé monument du patrimoine français le 17 novembre 1903. L'actuel musée de Béjaïa situé à l'intérieur du Fort Bordj Moussa, occupe une grande salle au rez-de-chaussée. Quelques tableaux ornent ses murs, et des stèles datant de l'époque romaine accueillent le visiteur. Un étalage de pierres taillées de la période néolithique, outils, bijoux de la période préhistorique s'étalent sous les bacs vitrés auprès de grattoirs, hachoirs, etc...dons d'un historien Debroudj, qui, au dire des uns, avait retrouvé ces objets dans une ancienne grotte: la grotte d'Ali-Bacha sur le mont de Gouraya (grotte située approximativement, et dont on ne retrouve aucune trace). On retrouve aussi, dans la collection de ce même historien, des ossements humains, et d'animaux, des perles, et des os d'autruche. L'époque romaine sera représentée par des stèles épitaphes, de la poterie, des vases funéraires, des fragments de mosaïque, des pièces de monnaie, et la collection en plâtre des Raïs Numides, la monnaie Hammadite et Almohade illustrent l'époque médiévale. On retrouvera aussi, dans ce musée, des objets plus récents: pièces de monnaie, poterie, sculpture... Pour la sculpture, le musée de Béjaïa peut se vanter d'avoir la fameuse Néo-bid de Camille Claudel (pièce principale du musée), qui représente une femme blessée au sein droit par une flèche. Elle est inspirée d'une légende grecque. D'autres sculptures existent aussi dans ce musée: celle de Just-Becquet (Samson et Dalila), de J. Esconla (Satire), et de S. Erica (Foehr), une copie du voilier italien qui a fait naufrage sur les côtes de Jijel, le buste de l'empereur Caracola fils de Sep time le Sèvre. Le musée détient aussi, une collection de peintures d'Emile Aubry (peintre français né à Sétif) et autres peintures anciennes et contemporaines. Malheureusement, ces tableaux n'ont pu être exposés par manque d'espace. Un projet d'ailleurs, est en cours pour la construction d'une soupente qui sera aménagée en galerie d'art.
