Abstract Purpose: Monopolar spindle 1 (MPS1) kinase inhibitor, BAY 1217389 (BAY) synergizes with paclitaxel. This phase I study assessed the combination of BAY with paclitaxel using a novel randomized continuous reassessment method (rCRM) to improve dose determination. Patients and Methods: Patients with solid tumors were randomized to receive oral BAY (twice daily 2-days-on/5-days-off) with weekly paclitaxel (90 mg/m2) or paclitaxel monotherapy in cycle 1. Dose escalation was guided by CRM modeling. Primary objectives were to assess safety, establish the MTD of BAY, and to evaluate the pharmacokinetic profiles for both compounds. Simulations were performed to determine the contribution of the rCRM for dose determination. Results: In total, 75 patients were enrolled. The main dose-limiting toxicities were hematologic toxicities (55.6%). The MTD of BAY was established at 64 mg twice daily with paclitaxel. Inclusion of a control arm enabled the definitive attribution of grade ≥3 neutropenia to higher BAY exposure [AUC0–12 (P< 0.001)]. After determining the MTD, we included 19 patients with breast cancer at this dose for dose expansion. Other common toxicities were nausea (45.3%), fatigue (41.3%), and diarrhea (40.0%). Overall confirmed responses were seen in 31.6% of evaluable patients. Simulations showed that rCRM outperforms traditional designs in determining the true MTD. Conclusions: The combination of BAY with paclitaxel was associated with considerable toxicity without a therapeutic window. However, the use of the rCRM design enabled us to determine the exposure–toxicity relation for BAY. Therefore, we propose that the rCRM could improve dose determination in phase I trials that combine agents with overlapping toxicities.