This paper presents an automatic image annotation approach that integrates the Naive Bayes classifier with particle swarm optimization algorithm for classes' probabilities weighting. The proposed hybrid approach refines the output of multi-class classification that is based on the usage of Naive Bayes classifier for automatically labeling images with a number of words. Each input image is segmented using the normalized cuts segmentation algorithm in order to create a descriptor for each segment. One Naive Bayes classifier is trained for all the classes. Particle swarm optimization algorithm is employed as a search strategy in order to identify an optimal weighting for classes probabilities from Naive Bayes classifier. The proposed approach has been applied on Corel5K benchmark dataset. Experimental results and comparative performance evaluation, for results obtained from the proposed approach and other related researches, demonstrate that the proposed approach outperforms the performance of the other approaches, considering annotation accuracy, for the experimented dataset.