Il est réélu dans la même circonscription en 1995 et est nommé au Conseil exécutif du Nouveau-Brunswick, dans le gouvernement de Frank McKenna. Il est d'abord Ministre d'État aux Affaires intergouvernementales et amérindiennes jusqu'en 1997, le seul à avoir jamais occupé ce poste. Il devient ministre de l'Éducation et ministre de la Justice et Procureur général la même année. Il reste ministre de l'Éducation dans le gouvernement de Ray Frenette en 1997. Il quitte le conseil en 1998, se portant candidat à la chefferie du Parti libéral. Bien qu'il ne soit pas élu, le Premier ministre Camille Thériault le nomme à nouveau ministre de l'Éducation, poste qu'il conserve jusqu'en 1999.
Bernard Richard est réélu dans la circonscription de Shédiac-Cap-Pelé durant l'élection générale de 1999, obtenant la plus forte majorité de tous les candidats, même si son parti ressort affaibli de l'élection. Lorsque Camille Thériault démissionne de son poste de chef du Parti libéral en 2001, Bernard Richard devient chef par intérim et du même coup chef de l'Opposition. Lorsque Shawn Graham est élu chef du parti en 2002, Bernard Richard est nommé leader parlementaire et critique des finances. Il maintient ces postes clés à la suite de sa victoire durant l'élection générale de 2003.
