Categorical time series are time-sequenced data in which the values at each time point are categories rather than measurements. A categorical time series is considered stationary if the marginal distribution of the data is constant over the time period for which it was gathered and the correlation between successive values is a function only of their distance from each other and not of their position in the series. However, there are many examples of categorical series which do not fit this rather strong definition of stationarity. Such data show various nonstationary behavior, such as a change in the probability of the occurrence of one or more categories. In this paper, we introduce an algorithm which corrects for nonstationarity in categorical time series. The algorithm produces series which are not stationary in the traditional sense often used for stationary categorical time series. The form of stationarity is weaker but still useful for parameter estimation. Simulation results show that this simple algorithm applied to a DAR(1) model can dramatically improve the parameter estimates.