It is recognized that hazardous emissions produced from frying oils may be related to oil properties, particularly the fatty acid composition. However, investigations have been limited and partial. In this work, the emissions from deep-frying foods with three oils (palm, olive, and soybean oils) with distinct fatty acid profiles were comprehensively examined in a simulated kitchen, and the interrelationship among emitted substances, oil quality parameters, and fatty acids profiles was explored. Firstly, palm oil emitted the highest number concentration of total particle matters ((3895 ± 1796) × 103 #/cm3), mainly in the Aitken mode (20–100 nm). We observed a positive correlation between particle number concentration and levels of palmitic acid, a major saturated fatty acid (SAFA) (rs = 0.73, p < 0.05), and total polar compounds (TPC) (rs = 0.68, p < 0.05) in the fried oil, a degradation marker which was also positively correlated with that of black carbon (BC) (rs = 0.68, p < 0.05). Secondly, soybean oil emitted the highest level of gaseous aldehydes (3636 ± 607 μg/m3), including acrolein, propinoaldehyde, crotonaldehyde, hexanal, and trans-2-heptenal; the total aldehyde concentration were positively correlated with α-linolenic acid (ALA) percentage (rs = 0.78, p < 0.01), while hexanal and trans-2-heptenal were with linoleic acid (LA) (rs = 0.73 and 0.67, p < 0.05). LA and ALA were two major polyunsaturated fatty acids in non-tropical plant oils. Thirdly, palm oil emitted the most particle-bound polycyclic aromatic hydrocarbons (PAHs), and a positive association was discovered between two PAHs and SAFA percentage. Olive oil seems superior to soybean and palm oils with regards to toxic emissions during deep-frying.