Au début du XVème siècle, le vidomnat (charge administrative et de police) de Monthey était aux mains de la famille de Monthéolo, qui fit construire une maison forte à l'emplacement du château actuel. Ainsi, en 1445, Louis de Monthéolo exerçait sa juridiction dans sa maison flanquée de deux tours. Après avoir appartenu à diverses familles, il fut racheté par l'Etat du Valais durant l'occupation haut-valaisanne, et devint résidence des gouverneurs dès 1547.
Le 6 février 1606, il brûla avec une partie de la ville. Le gouverneur Antoine Waldin le fit reconstruire presque à neuf en 1607. Des réparations importantes furent nécessaires en 1664. Depuis, le bâtiment n'a plus subi de modifications importantes, mais il ne reste de la construction primitive que des pans de murs et probablement la cour avec les vieilles arcades. Les tours et le corps de logis ont disparu, sans doute à la suite de l'incendie, puis des réparations et transformations.