Physical inactivity is the biggest health problem of this millennium and promoting regular physical activity by primary care physicians is considered to have pivotal role to combat modern-day non-communicable diseases. This study aimed to assess the attitudes and barriers of primary care physicians toward promoting regular physical activity to patients in Prince Sultan Military Medical City, Riyadh, Saudi Arabia. This cross-sectional study was conducted between January 2015 and July 2015 at Prince Sultan Military Medical City Riyadh, Saudi Arabia. Using a structured questionnaire, a total of 80 participating primary care physicians were evaluated for their attitudes and perceived barriers toward promoting physical activity to patients. The data were analyzed using SPSS software. Physicians considered health promotion in general (n = 78; 97.5%) and promoting physical activity - in particular (n = 80; 100%) constituted the overwhelming majors of the participants since they considered such promotion as an important part of the primary care. Advice to increase physical activity was given to patients by most participants and most considered themselves effective health promoters. Lack of time (n = 58; 72.5%), patients ignoring the physician’s recommendations (n = 52; 65%), and insufficient educational materials for patients (n = 43; 53.8%) were most frequently perceived as barriers to promoting physical activity by primary care physicians. The attitudes of primary care physicians were found to be consistent with expectations. However, consideration should be given to overcome perceived barriers to achieve health goals associated with promoting regular physical activity.