Foi mandado construir em 1420 pelo conde de Barcelos, D. Afonso, filho bastardo de D. João I. O desenho do paço inspirou-se fortemente nas grandes casas senhoriais francesas. Entre 1937 e 1959, foi alvo de profundas obras de restauro e reedificação com resultados algo polémicos sobre os critérios adotados relativamente à sua reconstituição.
Atualmente, o paço está convertido em palácio-museu.
É um castelo apalaçado característico dos fins da Idade Média, construído na primeira metade do séc. XV, por D. Afonso, 8º Conde de Barcelos, 1º duque de Bragança. As suas 4 chaminés com altos canudos simbolizavam a casa mais rica de Barcelos.
Faltam às ruínas de hoje algumas partes importantes deste castelo apalaçado, tais como a torre que se prolongava sobre a entrada da ponte e 3 das 4 chaminés com canudos altos.
A sua ruína ter-se-á iniciado a partir do séc. XVIII.
Instalado neste espaço, o Museu Arqueológico de Barcelos foi criado oficialmente em 1920. Já antes desta data se utilizava a área das ruínas do Paço dos Condes para guardar peças lícitas de cariz arqueológico que eram encontradas por todo o concelho, de épocas muito distintas, fruto de achados ocasionais ou provenientes do desmantelamento de monumentos arquitectónicos. Do seu espólio destaca-se ainda o Cruzeiro do Galo, ex-libris de Barcelos.