As obras do Paço iniciaram-se em maio de 1596 e terminaram em 1598, conforme se pode observar no portal maneirista do terreiro de entrada com uma inscrição lapidar com as armas da Casa de Bragança a que pertencia o bispo D. Nuno de Noronha, que ordenou a edificação deste edifício.
O sucessor, o bispo D. Afonso Furtado de Mendonça, dispendeu elevadas verbas para adquirir a quinta, o bosque e a tapada que se encontravam juntas ao paço, bem como o olival, a vinha e outros bens que tinham sido postos em hasta pública para liquidar as dívidas contraídas por D. Nuno de Noronha para a realização da ambiciosa obra. Regularizadas as contas, foi o conjunto doado ao bispo sucessor, D. Francisco de Castro. Desde esse momento e durante quase cem anos, não foram feitas obras de destaque pelos bispos eleitos.
D. João de Mendonça é o prelado seguinte a incluir melhoramentos; enriquece o interior do paço com mobiliário, tapeçarias, pinturas de mestres portugueses, biblioteca erudita, faianças, porcelanas, etc. (provavelmente este esforço de valorização do paço corresponde a bens pessoais daquele prelado - filho dos condes de Vale de Reis). Entretanto, a dimensão do bispado da Guarda e respetiva dificuldade das visitas pastorais provocaram a sua divisão, concedida pelo Papa Clemente XIV, em 1771, criando-se desse modo a diocese de Castelo Branco.
Foi o seu primeiro bispo D. Fr. José de Jesus Maria Caetano e o Paço de Castelo Branco passou a ser residência permanente dos bispos. O bispo seguinte, D. Frei Vicente Ferrer da Rocha, realiza obras importantes, nomeadamente, o corpo edificado a norte que inclui escadaria e a porta nobre, a ampla varanda, a colunata, balaústres e o excelente salão de entrada.
O espólio do edifício aumenta e, em 1786, os novos arranjos atingem os jardins, pomar, quinta, bosque; em 1798 é a vez do portal, designado a Porta de Roma, de acesso ao parque. Um revés considerável ocorre durante a presença dos franceses, Junot ocupa o Paço Episcopal. A decadência do Paço iria continuar, o bispo D. Joaquim de Miranda Coutinho pouco ou nada faz para a conservação da residência episcopal e, depois da sua morte (em 1831), a situação agrava-se.
A partir de 1835, com a passagem de diversos organismos como o governo civil para as suas instalações, foi desaparecendo parte do seu acervo e mobiliário. Com a extinção do bispado de Castelo Branco, em 1882, (anexado ao de Portalegre) e com a proclamação da República, em 1910, os bens diocesanos estiveram em risco de serem levados para Coimbra não fosse a oposição da população local. O edifício serviu de escola do magistério, de liceu, de escola técnica, até que, em 1964, a Direção dos Monumentos Nacionais decidiu adaptá-lo a Museu Regional.
A frontaria do Paço ergue-se diante de um amplo terreiro e no andar nobre mostra altos frontões barrocos, sendo de destacar o peristilo.
Na fachada posterior abrem-se três arcos abatidos (atualmente envidraçados) da galeria a partir da qual se podem contemplar os belos jardins. No interior diversas salas apresentam excelentes tetos, sendo de salientar a magnífica pintura decorativa do teto da Capela privativa, e ainda os dois belos retábulos de talha dourada que ali se encontram. No piso inferior, as divisões que prestavam serviços ao Paço, são na sua maioria abobadadas, e têm expostas diversas coleções e peças arqueológicas epigrafadas. No andar nobre destaca-se o grande salão paçal utilizado atualmente como sala de conferências. Em várias salas observam-se silhares de azulejos seiscentistas.
Anexo ao Paço Episcopal, no que resta da quinta de recreio, com mata e horto, o jardim, é, no dizer de muitos especialistas, um dos mais belos do mundo. De gosto italianizante, deveu o seu traçado a D. João de Mendonça. Tem uma forma retangular (40 metros por 55 metros) e é dominado por balcões e varandas com guardas de ferro e balaústres de cantaria. Dispõe de cinco lagos, com bordos de cantaria, nos quais estão montados jogos de água, de belo efeito.
Por entre canteiros de buxo, erguem-se estátuas de granito sobre peanhas de cantaria. De entre elas, destacam-se os quatro Novíssimos do Homem, as quatro Virtudes Cardeais, as três Virtudes Teologais, os Signos do Zodíaco, as cinco Partes do Mundo e as quatro Estações do Ano. Sobre os balaústres dos balcões e escadarias, figuram as estátuas do conde D. Henrique, dos reis de Portugal até D. José, dos doze Apóstolos, dos quatro Evangelistas, do Cardeal D. Henrique e dos três Filipes de Espanha (estes últimos quatro, a uma escala mais pequena). O jardim é abrigado a Norte pelo edifício do Paço e enquadrado a Sul pelo Lago das Coroas e por um tanque floreado - o Jardim Alagado, que têm centrados repuxos de cantaria, constituídos cada um por três peixes entrelaçados e encimados por uma coroa.