Od počátku 8. století do roku 1228 bylo pod muslimskou nadvládou, s výjimkou let 1162–1167. V letech 1250–1267 o území bojovalo Portugalské království s Kastilií, která se nakonec oblasti vzdala. V roce 1517 Beja získala městská práva a 10. července 1770 ji papež Klement XIV. učinil sídlem diecéze. V roce 1808 město vyplenily napoleonské jednotky pod vedením generála Andoche Junota.
Pamětihodnosti
Hrad
Hrad na vrcholu kopce dominuje městu. Spolu s opevněním byl postaven králem Denisem Portugalským ve 12. století na pozůstatcích římského castellum. Skládá se ze stěn se čtyřmi čtvercovými věžemi a centrální věží (Torre de Menagem), která je s výškou 40 metrů nejvyšší v Portugalsku. Vrchol věže je dosažitelný po 197 schodech. Z věže je na opevnění, které mělo kdysi 45 věžiček a 5 bran. Hrad v současnosti slouží jako malé vojenské muzeum.
Náměstí uprostřed hradu je pojmenované po Gonçalo Mendes da Maia zvaném O Lidador, rytíři, zabitého při bitvě s Maury v roce 1170.
Katedrála
Katedrála svatého Jakuba (Sé Catedral de São Tiago Maior) v sousedství hradu byla postavena kolem roku 1590.
Vizigótské muzeum
Bílý latinsko-vizigótský kostel Santo Amaro, zasvěcený svatému Amarovi, který stojí hned u hradu, je jedním ze čtyř předrománských kostelů v Portugalsku. Dnes je to muzeum vizigótského umění.
Muzeum Rainha D. Leonor
Regionální muzeum bylo založeno v letech 1927 a 1928 na místě předchozího kláštera řádu Convento de Nossa Senhora da Conceição, rozpuštěného v roce 1834. Tento františkánský klášter byl založen v roce 1459 infantem Fernandem, vévodou z Viseu a Beji. Výstavba trvala do roku 1509. Muzeum vlastní sbírku vlámského, španělského a portugalského malířství z 15.–18. století.
Archeologická sbírka muzea zahrnuje například vizigótské a římské artefakty, vykopávky z doby bronzové.