Les origines du monastère Santa Scolastica se perdent dans la nuit des temps. Cette zone était déjà occupée à l’âge du Bronze, comme le prouvent les restes d’une cabane sous les murs du bastion. Toutefois on estime que le bâtiment a été fondé avant l’an Mille ; un historien de Bari, Beatillo, fixe la date de construction de l’ensemble à l’an 755, à savoir à l’époque carolingienne, et plus précisément sous la papauté d’Etienne II. Nous savons que le monastère bénédictin intitulé à la Santissima Trinità, considéré l’ancêtre du monastère Santa Scolastica, était déjà construit en 1053. La même année, en effet, ce monastère et son abbé Marco sont cités dans une Bulle du pape Léon IX. En 1081, l’abbé Marco décida de fonder, près des murs de la cité côté nord, une église dédiée aux saints Jean et Paul, dont des restes ont été mis au jour sous les murs du bastion aragonais, là où se trouve actuellement la porte d’entrée du Musée Archéologique. De cet ancien édifice, il reste plusieurs tronçons de murs et des absides, les socles des piliers qui séparaient les nefs, et le splendide pavement en tesselles calcaires composant des formes géométriques. C’est à l’an 1102 que remonte l’installation des religieuses bénédictines de Cassino et c’est à la même date que le couvent a été dédié à sainte Scholastique. À l’époque, l’église était divisée en trois nefs, avec une abside centrale. En 1120 on y ajouta des dortoirs et un cloître ; l’abbesse Guisanda Sebaste fit agrandir et rénover l’ensemble. Sa tombe en marbre, aménagée dans un ancien sarcophage romain, se trouvait dans la salle du réfectoire.
En 1156, le complexe conventuel fut l’un des rares édifices publics de la ville à échapper à la destruction perpétrée par Guillaume le Mauvais, grâce à l’intercession de Giorgio Maione, amiral au service du roi normand et frère de l’abbesse Eustochia Maione. L’abbesse Marina accueillit de plus en plus de jeunes filles au couvent : les dons provenant des novices appartenant à des familles nobles de Bari enrichirent le patrimoine du monastère. Parmi les biens inestimables qu’il possédait, on compte le reliquaire en argent qui renferme un bras de l’apôtre saint Matthias ; ce reliquaire fait partie du butin du sac de Constantinople de l’an 1204. On raconte qu’après la cérémonie de remise de la relique, le 6 juin 1207, saint Matthias aurait accompli plusieurs miracles ; le plus célèbre concerne un mélange de pluie et de neige qui serait tombé sur le monastère le 5 août, après une longue période de sécheresse. On a confisqué le couvent après l’Unité d’Italie. Il a subit plusieurs transformations aux XIXe et XXe siècles, ainsi que de graves dégâts au cours de la seconde guerre mondiale. Pendant les travaux de restauration des années soixante-dix, on a découvert les ruines des bâtiments d’origine du monastère. La campagne de restauration la plus importante date de 2011 et n’est pas encore terminée ; elle a mis au jour des objets appartenant à des époques très anciennes.