This paper presents the earliest evidence for the exploitation of lignite (brown coal) in Europe and sheds new light on the use of combustion fuel sources in the 2nd millennium BCE Eastern Mediterranean. We applied Thermal Desorption/Pyrolysis-Gas Chromatography-Mass Spectrometry and Polarizing Microscopy to the dental calculus of 67 individuals and we identified clear evidence for combustion markers embedded within this calculus. In contrast to the scant evidence for combustion markers within the calculus samples from Egypt, all other individuals show the inhalation of smoke from fires burning wood identified as Pinaceae, in addition to hardwood, such as oak and olive, and/ or dung. Importantly, individuals from the Palatial Period at the Mycenaean citadel of Tiryns and the Cretan harbour site of Chania also show the inhalation of fire-smoke from lignite, consistent with the chemical signature of sources in the northwestern Peloponnese and Western Crete respectively. This first evidence for lignite exploitation was likely connected to and at the same time enabled Late Bronze Age Aegean metal and pottery production, significantly by both male and female individuals.