Crê-se que a cidade foi fundada, cerca de 400 a.C., pelos Celtas[3] ou mais provavelmente pelos Cónios, que a terão denominado Conistorgis, e que os Cartagineses lá se estabeleceram durante algum tempo. As primeiras referências a esta cidade aparecem no século II a.C., em relatos de Políbio e de Ptolomeu.
Com o nome alterado para Pax Julia, foi sede de um conventus (circunscrição jurídica) pouco depois da sua fundação, teve direito itálico e 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. Nesta altura passa a cidade a denominar-se Paca.
Do século VIII ao ano de 1162, esteve sobre a posse dos Árabes, designadamente no domínio dos Abádidas do Reino Taifa de Sevilha. No referido ano os cristãos reconquistado definitivamente a cidade. Recebeu o foral em 1524 e foi elevada a cidade em 1517.
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.