Background: Perceived harm, social influences, smoke-free policies, and media exposure have been understudied in relation to tobacco-related attitudes/behaviors in aggregate or in low and middle-income countries; thus, this study examined these factors collectively in relation to smoking-related outcomes among Armenian and Georgian adults. Methods: Using 2018 cross-sectional survey data (n = 1456), multivariable regression analyses examined these factors in relation to smoking status, perceived harm among nonsmokers, and readiness to quit and past-year quit attempts among smokers. Results: Significant predictors (p < 0.05) of current smoking (27.3%) included lower perceived harm, more smoking friends, and fewer home and vehicle restrictions. Among nonsmokers, more home and restaurant/bar restrictions, fewer vehicle restrictions, greater anti-tobacco media exposure, and less pro-tobacco media exposure predicted greater perceived harm. Among smokers, greater perceived social acceptability of smoking, less anti-tobacco media exposure, and greater pro-tobacco media exposure predicted readiness to quit (12.7% of smokers). More smoking friends, more home restrictions, less anti-tobacco media exposure, and greater pro-tobacco media exposure predicted past-year quit attempts (19.2%). Conclusions: Findings support the importance of smoke-free policies but were counterintuitive regarding the roles of social and media influences, underscoring the need to better understand how to address these influences, particularly in countries with high smoking rates.