The mechanism of formation of nanosized aerosol particles during mechanical grinding of coal from Kuzbass mines is studied. The concentration and size spectrum of aerosol particles in a mine tunnel during cutter operation were measured using an aerosol spectrometer. It is found that 90% of the particles are less than 200 nm in size. In the nanometer range, there are two peaks corresponding to average diameters of 20 and 150 nm, the first of which is due to single particles, and the second to aggregates consisting of single particles. The formation of aerosol during mechanical coal grinding in a continuous flow mill was studied. The spectrum and morphology of the particles produced in the laboratory mill are in qualitative agreement with those for the nanoaerosol formed in the mine. The influence of the coal aerosol on the combustion of gas mixtures was studied. Laboratory experiments showed that the presence of the nanoaerosol in a lean methane–air mixture significantly increased its explosibility. This was manifested in an increase in the maximum pressure and a significant increase in the pressure rise rate during explosion. The study leads to the conclusion that the nanoaerosol is formed from the organic coal components released into the gas phase during local heating of coal on the cutter teeth.