Six samples of propolis were analyzed in the paper: a sample from Brazil, Estonia, China and three samples from different locations of Uruguay. Static headspace technique coupled with gas chromatography-mass spectrometry analysis has been applied for the determination of the characteristic volatile profile with the aim to differentiate the propolis from different regions. Monoterpenes (α- and β-pinenes) were predominant in all samples, except the sample from China. This sample separated itself by the alcohols 3-methyl-3-buten-1-ol and 3-methyl-2-buten-1-ol, (40.33% and 11.57%, respectively) and ester 4-penten-1-yl acetate (9.04%). α-Pinene and β-pinene composed 64.59–77.56% of volatiles in Brazilian and Uruguayan propolis, and 29.43% in Estonian propolis. Brazilian propolis was distinguished by a high amount of β-methyl crotonaldehyde (10.11%), one of Uruguayan samples 3- by limonene (15.58%), and the Estonian sample - by eucalyptol (25.95%). Statistical investigation of the samples was made applying principal component, hierarchical cluster and K-Means cluster analyses. Various data pre-processing techniques were proposed and used to study and obtain the important volatile compounds contributed to the differentiation of the propolis samples from different regions to separate clusters.