Background Smoking is Greece's largest public health threat. Greece has the highest adult smoking prevalence among all E.U countries, which in turn possibly predisposes Greek children and adolescents to smoke. The purpose of our study was to research into the smoking habits of preschool children's parents since children of that age could be vulnerable to parental negative role modeling and to investigate into the necessity of conducting a public health awareness programme aimed at the general population. Methods A cross-sectional study was performed on the parents of children enrolled in kindergarten in western Crete-Greece (2809 parents), and interviewed during the 2004–2005 Cretan school health promotion programme. Results 63% of households had at least one parent a current smoker and in 26% both parents were found to be current smokers. Smoking prevalence among adults with preschool children was estimated at 44% (52% of fathers and 36% of mothers). Paternal education and nationality were statistically significantly related to smoking (p < 0.001), unlike place of residence (p = 0.862) and level of maternal education (p = 0.132). Conclusion Smoking prevalence is high even among parents with preschool children. Taking into account the parents' significant primary role in the children's upbringing and the effect that parental induced passive smoking has on children's health and health attitude; one can deduce that the health of Greek children is under threat. It is of major importance that educational and policy intervention measures are implemented to reduce such a situation that could contribute to promoting the initiation of smoking among Greek adolescents.