Background: The benefits of physical activity during pregnancy include lower maternal weight gain, a lower likelihood of gestational diabetes, low back pain, preeclampsia, preterm delivery, caesarian delivery, and macrosomia. This study aimed to examine the factors associated with insufficient leisure-time physical activity (LTPA) during the first trimester. Methods: A cross-sectional study was conducted at the Clinic for Obstetrics and Gynecology of Clinical Center of Serbia, Belgrade, between January and June of 2018. The final analyses included 162/175 pregnant women. The questionnaire was used to obtain social characteristics, pregnancy, and lifestyle characteristics (Pregnancy Risk Assessment Monitoring System—PRAMS), pre-pregnancy LTPA (International Physical Activity Questionnaire—IPAQ), and LTPA during the first trimester (Pregnancy Physical Activity Questionnaire—PPAQ). Women were classified into two groups of sufficient and insufficient LTPA during the first trimester based on the recommendations of the World Health Organization. Multivariate logistic regression analysis was applied. Results: A total of 27.2% of the women had insufficient LTPA during pregnancy. Insufficient LTPA during pregnancy was associated with <12 years of education (OR: 2.3, 95% CI: 1.05–5.04), self-rated financial status as poor (OR: 0.34, 95% CI: 0.14–0.79), and hours spent walking before pregnancy (OR: 0.87, 95% CI: 0.77–0.99). Conclusions: Our results can help direct health care professionals advice for women who are planning pregnancy towards walking as it seems to be sustained during pregnancy.