L'histoire du palais du parlement de Bretagne est intimement liée à celle du parlement de Bretagne. Depuis l'Acte d'Union qui rattacha la Bretagne à la France en 1532, ce parlement régional se déplaçait entre Vannes, Rennes et Nantes. Ce n'est qu'en 1561 que les sessions du parlement se fixèrent à Rennes.
Le manque de ressources financières et les guerres de religion retardèrent la construction du palais royal et les parlementaires siégèrent pendant 48 ans au couvent des Cordeliers. Ce n'est que lorsque la paix revint, sous le régime d'Henri IV, que de nouveaux fonds furent acquis, des lettres patentes octroyées par le roi en 1609 permettant de lever un nouvel impôt. En 1578, la ville de Rennes est autorisée à lever des impôts en vue de la construction d'un bâtiment pour le parlement, notamment un impôt sur les pots de cidre.
Le choix d'un site pour l'édification du palais du parlement fut difficile. Les membres du parlement préféraient être installés intra-muros, tandis que la ville désirait qu'il soit en dehors des murs. Elle proposa comme terrains les jardins de Touriel, situé entre la porte aux Foulons et la porte Saint-Georges, ce qui correspond actuellement à la rue de la Visitation. Par lettres patentes, le roi Henri IV avait donné son accord, mais le parlement ne céda pas. Le 2 novembre 1613, une commission fut nommée et un an plus tard, le choix fUt fait : le palais du parlement sera construit à la place des jardins situés au sud du couvent Saint-François et des immeubles adjacents à ceux-ci.
Le 15 septembre 1618, la première pierre est posée. Les plans sont d'abord dessinés par l'architecte de la ville Germain Gaultier mais son projet est rejeté par le Duc de Brissac et la commission de parlementaires et de membres de la Communauté de ville. Les plans sont revus par Salomon de Brosse, architecte royal ayant notamment travaillé sur le Palais du Luxembourg qui pour cela passa quinze jours à Rennes durant août 1618. Salomon de Brosse effectue des petits changements sur les travaux de Germain Gaultier : il reprend la façade du palais et les arcades de la cour mais les façades latérales restent identiques aux plans de Gaultier.
La direction du chantier est d'abord assurée par Germain Gaultier jusqu'à sa mort accidentelle en 1624, puis est reprise par Étienne Corbineau, entrepreneur lavallois. Les travaux sont ensuite interrompus par une épidémie de peste en 1627 ; ils ne reprennent qu'en 1640 sous la direction de Tugal Caris, maître d'œuvre lavallois, puis par Pierre Corbineau. Le chantier est à nouveau perturbé lors de la fronde parlementaire entre 1648 et 1649 et ce n'est qu'en 1654, que les travaux de gros œuvre sont achevés. Le 11 janvier 1655, la cour et les parlementaires s'y installent ; le doyen des présidents du parlement, Claude de Marbeuf, prend possession de l'édifice le 16 janvier 1655, mais la réalisation des décorations intérieures est pleinement achevée en 1709.
En 1720, après le grand incendie de Rennes, le cœur de la ville est reconstruit et le parlement, un des seuls bâtiments à ne pas avoir été détruit par l'incendie, notamment grâce à la mise en place de coupe-feux, se voit attribuer une place royale où trône une statue équestre de Louis XIV par Jacques V Gabriel. Le grand escalier qui menait aux étages nobles (le rez-de-chaussée était réservé aux communs et servait entre autres de prison) fut détruit à cette époque car, selon Jacques V Gabriel, « le palais doit s'incliner devant la statue de Louis XIV comme les parlementaires devant le roi ». La statue équestre fut démontée puis fondue par la suite durant la Révolution.
Durant tout le XIXe siècle, le bâtiment recevra diverses transformations ou restaurations. Sous Louis-Philippe, le palais est adapté à sa fonction de cour d'appel : un mur est ouvert au nord pour permettre l'entrée des fourgons de police par exemple. La décoration intérieure est restaurée durant le second Empire, mais c'est à la fin du XIXe siècle qu'une véritable restauration, dont le but est de retrouver l'aspect initial lors de la construction du palais, est entreprise par l'architecte Jean-Marie Laloy. C'est de cette époque que date l'inscription du bâtiment en tant que Monument historique. Au XXe siècle, une restructuration du palais de justice entraîne de nouveaux travaux : des bureaux supplémentaires sont aménagés au dernier étage en 1970 et dans les années 1980, cette restructuration s'accompagne d'une restauration de cinq ans.
En 1994, la baisse des prix du poisson, la dégradation des ventes et la concurrence des autres pays européens entraînent une crise des marins-pêcheurs bretons. À l'occasion de la visite du premier ministre Édouard Balladur, cinq mille personnes se déplacent à Rennes le 4 février 1994 et se trouvent bloquées devant la préfecture par les CRS. La manifestation dégénère en émeute lors de l'entrée dans le centre-ville : des pavés sont lancés, plusieurs vitrines de magasins sont brisées et de violentes confrontations avec les forces de l'ordre s'engagent. Néanmoins, la soirée voit les évènements se calmer.
Plusieurs fusées de détresse sont lancées à proximité du palais peu avant la fin de la manifestation. L'une d'entre elles brise une ardoise et se retrouve dans la charpente. L'alarme à incendie se déclenche, mais le gardien pense qu'elle est trop sensible et qu'elle s'est allumée à cause du vent, et n'alerte pas les autorités compétentes. Ce sont les passants qui préviennent les pompiers : deux appels successifs à 0h29 et 0h30 signalent l'incendie, suivi d'un appel de la police.
— Deuxième appel enregistré par les pompiers à minuit trente le 5 février 1994.
À 0h34, vingt pompiers arrivent sur place, mais l'importance de l'incendie incite le chef de garde à demander des renforts immédiats et à faire appel à l'officier de permanence. La majeure partie des pompiers de garde du district de Rennes se déplace sur les lieux, et trente minutes après le signalement de l'incendie, cinquante-deux hommes sont sur place.
L'incendie est attisé par un fort vent d'ouest et se propage rapidement dans toute la toiture. À 0h40, l'ensemble des combles sont embrasés, et les flammes risquent de se propager aux bâtiments voisins : six personnes habitant à proximité sont évacuées. Le réseau d'eau de la ville étant insuffisant pour alimenter les lances à incendie, des tuyaux sont déroulés pour pomper l'eau dans la Vilaine.
La totalité des moyens du district de Rennes est alors engagée, et des sapeurs-pompiers de tout le département d'Ille-et-Vilaine viennent prêter main forte aux équipes déjà en intervention : à 2h00 du matin, on compte sur place plus de cent cinquante sapeurs-pompiers et seize engins. Après avoir lutté à l'extérieur et autour du palais, les pompiers progressent à l'intérieur du brasier avec cinq lances, épaulés par une grande échelle à l'extérieur. A 2hl2, le feu est éteint. À 3h00, il ne reste plus que les murs de pierre : la toiture s'est effondrée sur le premier étage. Deux pompiers sont blessés lors de l'effondrement d'un plafond.
Tandis que l'incendie ravage la charpente, une étroite collaboration entre les sapeurs-pompiers, les architectes des bâtiments de France et le service des monuments historiques est entreprise afin de sauver le mobilier et les tapisseries du palais. Alain-Charles Perrot, architecte en chef des Monuments Historiques, désigne en urgence quelles sont les œuvres d'art à sauver dès que la maîtrise de l'incendie permit d'entrer dans l'édifice. L'accent est mis sur la protection de la Grand'Chambre, la pièce du palais la plus ouvragée, avec la brumisation des tapisseries par les pompiers.
Un poste de commandement situé sur la rue Hoche réunit Germaine et Christophe Amiot (ABF), Alain-Charles Perrot (ACMH), Nicolas Simonnet (CRMH) ainsi que des documentalistes et des agents de la Direction régionale des affaires culturelles et du musée des beaux-arts de Rennes afin d'organiser le sauvetage : tous les éléments sauvés, des tableaux jusqu'aux dossiers de la correctionnelle sont étiquetés et classés.
La mairie de Rennes fut elle-aussi acteur du sauvetage : lorsque l'incendie fut définitivement maîtrisé, une soixantaine d'agents des services municipaux aidèrent à évacuer les œuvres du palais. La ville fournit également du matériel (camions, conteneurs, casques...) et les locaux de stockage. L'armée, et notamment le 16e régiment d'artillerie, ainsi que plusieurs entreprises du bâtiment prêtent main forte aux différentes équipes pour déblayer et sécuriser le bâtiment : outre les dégâts sur le mobilier, la structure entière du palais est déstabilisée.
La plus grande partie des tapisseries et des œuvres d'art a pu être sauvée. En novembre 1994, la décision est prise de reconstruire le bâtiment à l'identique et les travaux débutent deux ans plus tard. La restauration du palais dura trois ans et coûta 35 millions d'euros. Selon une autre source, le montant des travaux se découpe de la façon suivante :
Restauration et reconstruction du bâtiment | 19,82 millions d'euros |
Restauration à l'identique des salles | 19,82 millions d'euros |
Réaménagement de la cour d'appel | 15,24 millions d'euros |
Total | 54,88 millions d'euros |