Com a conquista romana, esta cidade passa a fazer parte do Império Romano (mais especificamente da República Romana), ao qual pertenceu durante mais de 600 anos, primeiro na província da Hispânia Ulterior e posteriormente na província da Lusitânia. Com o nome alterado para Pax Julia, foi sede de um conventus (circunscrição jurídica) pouco depois da sua fundação romana - o Convento Pacense (em latim: Conventus Pacensis), também teve direito itálico. Esta cidade albergou uma das quatro chancelarias da Lusitânia, criadas no tempo de Augusto. A sua importância é atestada pelo facto de por lá passar uma das vias romanas.
Os Alanos, Suevos e os Visigodos dominaram esta cidade depois da queda do Império Romano, tornando-a sede de bispado. No século V, depois de um breve período no qual haverá sido a sede da Tribo dos Alanos, os Suevos apoderaram-se da cidade, sucedendo-lhes os Visigodos. Nessa época a cidade passa a denominar-se Paca.
Do ano 714 (século VIII) ao ano de 1162 (meados do século XII), durante mais de 400 anos, esteve sob a posse dos Árabes, primeiro sob o Califado de Córdova e mais tarde sob domínio dos Abádidas do Reino Taifa de Sevilha, que lhe alteraram o nome para Baja ou Beja (existe outra cidade com este nome na Tunísia), uma alteração fonética de Paca (a língua árabe não tem o som "p").
Aqui nasceu o Al-Mutamid, célebre rei-poeta que dedicou muitas das suas obras ao amor a donzelas e também a mancebos homens.
No referido ano de 1162 os cristãos reconquistaram definitivamente a cidade. Recebeu o foral em 1524 e foi elevada a cidade em 1517. Beja foi o berço da notável família de pedagogos e humanistas do Renascimento que incluiu Diogo de Gouveia (1471 - 1557), professor de Francisco Xavier e conselheiro dos reis D. Manuel I e D. João III de Portugal, a quem recomendou a vinda dos jesuitas; André de Gouveia (1497 - 1548), humanista, reitor da Universidade de Paris e fundador do Real Colégio das Artes e Humanidades em Coimbra e o humanista António de Gouveia.
Criado pelo Rei D. Afonso V de Portugal em 1453, o título de Duque de Beja foi atribuído ao segundo filho varão, até à instituição da Casa do Infantado, em 1654, pelo Rei D. João IV, tendo-o como base.
A cidade manteve-se pequena os séculos seguintes, sendo muito destruída durante as Invasões Francesas entre 1807 e 1811. A partir do século XX notou um certo desenvolvimento económico, como a contrução de escolas (o novo Liceu em 1937), o novo Hospital (1970), assim como novas instalações judiciais e comerciais, embora muito do seu património antigo tenha sido destruído pelas novas construções, nomeadamente no centro histórico. Em 2011 foi inaugurado o Aeroporto de Beja sendo que no entanto a grave crise económica motivou a que este se mantivesse em fraco funcionamente e em situação de quase fecho.