This study seeks to investigate the nature of fiscal policy regime in Kenya, and the extent to which fiscal policy is sustainable in the long run by taking into account periodic regime changes. Markov-switching models were used to determine fiscal policy regimes endogenously. Regime switching tests were used to test whether the No-Ponzi game condition and the debt stabilizing condition were met. The results established that the regime-switching model was suitable in explaining regime sustainable and sustainable cycles. An investigation of fiscal policy regimes established that both sustainable and unsustainable regimes were dominant and each lasted for an average of four years. There was evidence to suggest the existence of procyclical fiscal policy in Kenya. Regime switching tests for long-run sustainability suggested that the No-Ponzi game condition weakly holds in the Kenyan economy. Regime-based sensitivity analysis suggests that the persistence of unsustainability regime for more than four years could threaten long-run fiscal sustainability. Sensitivity tests are conducted by resorting to (i) Self-Exciting Threshold Autoregressive Models at the country-level, and (ii) non-linear Granger causalities across a Feed- Forward Artificial Neural Network composed of East-African countries (Burundi, Kenya, Rwanda, Tanzania and Uganda).