Background: Sedentary behavior (SB) and lack of physical activity (PA) have been associated with poorer health outcomes and are increasingly prevalent in individuals working in sedentary occupations such as office jobs. Gamification and nudges have attracted attention as promising strategies to promote changes in health behavior. However, most effectiveness studies thus far lacked active controls, and few studies have tested interventions combining these strategies. Objective: This study investigates the effectiveness of combining a gamified digital app with physical nudges to increase PA and reduce SB in Dutch office workers. Methods: Employees in the municipality of Rotterdam (N=298) from two office locations were randomized at the location level to either a 10-week intervention, combining a 5-week gamification phase encompassing a gamified digital app with social support features and a 5-week physical nudges phase, or to an active control (ie, basic digital app with self-monitoring and goal setting). The primary outcome was the daily step count, objectively measured via accelerometers. Secondary outcomes were self-reported PA and SB measured at baseline and at 5, 10, and 14 weeks. Mixed effects models were used to analyze the effects of the intervention on the outcome measures. Results: A total of 78.5% (234/298) of participants completed the study and provided accelerometer data, whereas 36.9% (110/298) participants completed the self-report measures at 14 weeks. In the gamification phase, step count data were missing for 13.5% (473/3492) of observations in the control and 11.4% (445/3888) in the intervention condition; however, these percentages increased to 39.6% (1154/2910) and 59.6% (1932/3492) at follow-up, respectively. During the gamification phase, intervention participants increased their number of daily steps by 634 (95% CI 154.2-1113.8; P=.01) more than participants in the control group, after controlling for relevant factors. Improvements were not sustained during the physical nudges phase (P=.76) or follow-up (P=.88). Conclusions: A digital intervention with gamification and social support features significantly increased the step count of office workers compared with an active control. Physical nudges in the workplace were insufficient to promote the maintenance of behavioral changes achieved in the gamification phase. Future research should explore the long-term effectiveness of similar gamified digital interventions.