Background: Smoking cessation counseling is not well established in Middle East countries including Palestine. This study assesses the practice of smoking cessation counseling among primary healthcare (PHC) physicians in Palestine and its determinants. Methods: Over the period from April to September 2019, general practitioners, family medicine physicians, obstetricians and gynecologists, and dentists working at the PHC Centers in Palestine were approached through a cross-sectional design using a self-reported questionnaire. Proportionate stratified random sampling approach has been used. Sociodemographic, medical background, smoking cessation counseling training, smoking history, practice, knowledge, attitude, and confidence were evaluated. The proportion of favorable practice has been determined and its relationship with all variables has been evaluated. Ethical approval was received from the National University of An-Najah. Results: 295 physicians were enrolled in the study with an 86% response rate. 75.5% (n = 222) were males with a mean age of 39.9 ± 9 years. The majority were General Practitioners (76.5%, n = 252). Most of them (84.3%, n = 215) had not received any training. The favorable practice was seen in 36.6% (95% CI 31–41%). Attitude is the main predictor of favorable practice (P value = 0.002, adjusted OR = 1.1). Conclusion: Palestinian PHC physicians have a low level of counseling for smoking cessation. Given the efficacy of counseling for smoking cessation and the high level of the tobacco epidemic in the area, health policy to ensure all healthcare personnel-especially physicians-receive training in cessation counseling and call for a public health campaign for control of tobacco should be taken into account.