Dieser Ort hat den Namen gewechselt, weil seine Burg ihn aufgefressen hat. Der erste Ortsname erscheint in einer Verkaufsurkunde von 958, bewahrt in der Abtei Cava de' Tirreni, die von einem Grundstück in locum ziziro spricht; die Wurzel Ziz ist arabisch und bedeutet prächtig, lieblich — dieselbe, die in der Zisa von Palermo steckt — und führt in die Zeit des Emirats von Bari zurück, als die Sarazenen die Stadt und gut zwanzig Festungen ringsum hielten. Im Jahr 1077 heißt der Ort noch Siziro. Dann kommen die Normannen, am Ende des elften Jahrhunderts: sie finden die Reste eines älteren Burgbaus — ein Viereck mit vier runden Ecktürmen, und niemand kann sagen, wer ihn errichtet hat —, bauen ihn mit dessen Steinen wieder auf, und Umfredo und Guglielmo d'Altavilla taufen ihn San Nicandro, wie es ihre Gewohnheit war, denn sie kamen aus San Nicandro di Sicignano degli Alburni. Der Name gehörte der Burg, nicht dem Ort; doch in den bischöflichen Urkunden von 1172 erscheint Siziro nicht mehr, und es steht nur noch San Nicandro. Die Burg hatte sich auch den Ort genommen. Der Zusatz «di Bari» stammt dagegen von 1863.
Von jener Burg weiß man viel, weil die Urkunden davon erzählen. Im Jahr 1119 schenkte Emma d'Altavilla, die sich in Santa Severina aufhielt, die Zehnten des Lehens dem Abt von Montescaglioso unter einer Bedingung: dass er einen Kaplan schicke, um in der kurz zuvor innerhalb der Mauern erbauten Kapelle San Nicola die Messe zu lesen. Eine Urkunde von 1146 beschreibt den Ort, wie er war: die Burg hat nun acht Türme, eine unregelmäßige viereckige Ringmauer und einen Graben, die Kapelle im Innern, und der Ort liegt rings um sie. Zu Beginn des dreizehnten Jahrhunderts wird sie noch einmal erweitert, mit einem neuen Palast, Ställen, Lagerhäusern, einem weiteren Graben und neuen Toren, denn das Lehen war reich an Getreide und Vieh und lag am kürzesten Weg zwischen Bari und Matera: die Burg wurde zu einer Grangie, also zu einem Lager, das die Kreuzfahrer in Übersee versorgte. Als das Unternehmen vorbei war, schenkte König Karl II. sie am ersten November 1304 zur Gänze der Basilika San Nicola in Bari. Bei den Grabungen kamen byzantinische Münzen zutage und ein goldener Tarì mit einer Legende in kufischen Schriftzeichen. Hier wurde der Philosoph Domenico Losurdo geboren.