History matching is the process of integrating dynamic production data in the reservoir model. It consists in estimation of uncertain model parameters such that oil or water production data from flow simulation become close to observed dynamic data. Various optimization methods can be used to estimate the model parameters. Simultaneous perturbation stochastic approximation (SPSA) is one of the stochastic approximation algorithms. It requires only two objective function measurements for gradient approximation per iteration. Also parameters estimated by this algorithm might converge to their true values under arbitrary bounded additive noise, while many other optimization algorithms require the noise to have zero mean. SPSA algorithm has not been well explored for history matching problems and has been applied only to simple Gaussian models. In this paper, we applied SPSA to history matching of binary channelized reservoir models. We also used SPSA in combination with parameterization method CNN-PCA. And we considered the case of complex noise in observed production data and with objective function that does not require assumptions of normality of the observations, which is common in history matching literature. We experimentally showed that SPSA method can be successfully used for history matching of non-Gaussian geological models with different types of noise in observations and outperforms Particle Swarm Optimization by convergence speed.