Multimodal mobility systems provide seamless travel by integrating different types of transportation modes. Most existing studies model service operations and users’ travel choices independently or iteratively and constrained with pre-defined multimodal travel options. The paper proposes a choice-based optimization approach that optimizes service operations with explicitly embedded travelers’ choices described by the multinomial logit (MNL) model. It allows the flexible combination of travel modes and routes in multimodal mobility systems. We propose a computationally efficient linearization method for transformed MNL constraints with bounded errors to solve the choice-based optimization model. The model is validated using a mobility on demand and public transport network by comparing it with a simulation sampling-based MNL linearization method. The results show that the mixed-integer formulation provides a high-quality solution in terms of both the estimated choice probability errors and computational speed. We also conduct an error analysis and a sensitivity analysis to explore the behavior of the proposed approach. The real-world case study in Stockholm further illustrates that the analytical formulation achieves a better system operation performance than the traditional iterative supply–demand updating optimization method. The choice-based optimization model and solution formulation are highly adaptable for operations decision support integrating stochastic travel choices in multimodal mobility systems.