The Markov chain random field (MCRF) theory provided the theoretical foundation for a nonlinear Markov chain geostatistics. In a MCRF, the single Markov chain is also called a “spatial Markov chain” (SMC). This paper introduces an efficient fixed-path SMC algorithm for conditional simulation of discrete spatial variables (i.e., multinomial classes) on point samples with incorporation of interclass dependencies. The algorithm considers four nearest known neighbors in orthogonal directions. Transiograms are estimated from samples and are model-fitted to provide parameter input to the simulation algorithm. Results from a simulation example show that this efficient method can effectively capture the spatial patterns of the target variable and fairly generate all classes. Because of the incorporation of interclass dependencies in the simulation algorithm, simulated realizations are relatively imitative of each other in patterns. Large-scale patterns are well produced in realizations. Spatial uncertainty is visualized as occurrence probability maps, and transition zones between classes are demonstrated by maximum occurrence probability maps. Transiogram analysis shows that the algorithm can reproduce the spatial structure of multinomial classes described by transiograms with some ergodic fluctuations. A special characteristic of the method is that when simulation is conditioned on a number of sample points, simulated transiograms have the tendency to follow the experimental ones, which implies that conditioning sample data play a crucial role in determining spatial patterns of multinomial classes. The efficient algorithm may provide a powerful tool for large-scale structure simulation and spatial uncertainty analysis of discrete spatial variables.