Introduction: Despite the high prevalence of smoking in the former Soviet Union (fSU), particularly among men, there is very little information on nicotine dependence in the region. The study aim was to describe the prevalence of nicotine dependence in 9 countries of the fSU and to examine the psychosocial factors associated with nicotine dependence. Methods: Cross-sectional, nationally representative surveys using multistage random sampling were conducted in 2010 with men and women aged 18 years and over in Armenia, Azerbaijan, Belarus, Georgia, Kazakhstan, Kyrgyzstan, Moldova, Russia, and Ukraine. The main outcome of interest was nicotine dependence using the Fagerstrom Test for Nicotine Dependence. Multivariate regression analysis was then used to explore the influence of a range of psychosocial factors on higher nicotine dependence. Results: Mean nicotine dependence among men in the region as a whole was 3.96, with high dependence ranging from 17% in Belarus to 40% in Georgia. Among women, mean dependence was 2.96, with a prevalence of high dependence of 11% for the region. Gender (men), younger age of first smoking, lower education level, not being a member of an organization, bad household economic situation, high alcohol dependence, and high psychological distress showed significant associations with higher nicotine dependence. Conclusions: High nicotine dependence among men was recorded in a number of study countries. Findings highlight the need for tobacco programmes to target early age smokers and less educated and poorer groups and suggest common ground for programmes seeking to reduce nicotine dependence, harmful alcohol use, and psychological distress.