Sous la direction de John Major, dont il devient un allié clé, Heseltine devient président de la Chambre de commerce et, à partir de 1995, vice-premier ministre et premier secrétaire d'État.
Il a été nommé vice-premier ministre par John Major en 1995.