Automatic modulation classification (AMC) with multiple sensors is a challenging problem when the channel conditions are unknown at the receiver. In this paper, using the Markov chain Monte Carlo (MCMC) approach, we develop a novel algorithm for AMC when the amplitude and phase of the channel gains are unknown. Using sampling techniques, we marginalize over the unknown channel parameters that follow a certain probability distribution. This improves the estimate of the a posteriori distribution of the modulation formats, thereby improving the overall classification performance. Further, to overcome the problem of local extrema traps encountered in sampling algorithms, we introduce the idea of adding artificial noise beyond a certain threshold of signal-to-noise (SNR). This improves the performance of the sampling based AMC algorithm in the high SNR regime. Simulation results and comparisons are provided to show the efficiency of the proposed algorithm over the most related works in the literature.