Il Castello Tramontano è situato su una collinetta, chiamata collina di Lapillo, sovrastante il centro storico della città di Matera.
In stile aragonese, il Castello, con un maschio centrale e due torri laterali rotonde, smerlate e dotate di feritoie, fu fatto costruire a partire dal 1501 dal Conte Gian Carlo Tramontano, feudatario di Matera. Il nuovo Re di Napoli, Ferdinando II, aveva promesso ai Materani di non cedere più la città ad alcun feudatario, dopo che questa si era già liberata più volte dal giogo feudale pagando diversi riscatti per restare città libera ad autonomo reggimento, cioè dipendente direttamente dalla Corona Reale. Invece il Conte Tramontano, che vantava crediti nei confronti dell'Erario Reale, chiese ed ottenne la Contea di Matera nel 1496.
Il Conte si rese presto inviso ai Materani in quanto con il passare del tempo si riempì di debiti, per far fronte ai quali tassava la popolazione con gravose imposte. Cominciò così la costruzione del Castello, che era situato su una collina dominante la città, al di fuori delle mura cittadine, con lo scopo di controllo "feudale" dei terreni circostanti più che di difesa della città stessa. Pare che poi la costruzione avrebbe dovuto comprendere altre torri di difesa, una delle quali è stata rinvenuta sotto la centrale piazza Vittorio Veneto di Matera insieme ad altri ambienti ipogei. Per la costruzione del Castello furono spesi ben 25.000 ducati e ciò andò a gravare ancor di più sulla popolazione.
Fu così che alcuni cittadini, stanchi dei continui soprusi, si riunirono nascosti dietro un masso, che da allora fu chiamato u pizzon' du mal consigghj, cioè la pietra del mal consiglio, ed organizzarono l'assassinio. Il 29 dicembre 1514 il Conte, appena uscito dalla Cattedrale, fu assassinato in una via laterale della stessa, che fu successivamente chiamata in modo eloquente Via del Riscatto. Il Castello restò dunque incompiuto.
Dal 2008 è interessato, insieme al parco circostante, da lavori di restauro terminati nel 2011.