Tackling optimization in mixed domains (continuous and discrete decision variables) has recently gained attention, causing the development of various extensions of continuous optimization algorithms. In order to more accurately address the combinatorial nature of the discrete aspects of the search space, we go a different way and combine two algorithms, one for each aspect of the search space. Focusing, in the discrete part, on binary search spaces, we use Population-Based Incremental Learning (PBIL) for discrete optimization. We combine this algorithm with the Covariance Matrix Adaptation Evolutionary Strategy (CMA-ES) to address the continuous part. We compare our CMA-ES-PBIL with two leading variants of CMA-ES from the literature: CMA-ES with Margin (CMA-ESwM) and CMA-ES with Probability Distribution Model (CMA-ES-PDM). We conduct run time analysis on some separable and a non-separable benchmark functions and show that our hybrid algorithm significantly outperforms both CMA-ESwM and CMA-ES-PDM. Our results also show that the binary part is optimized much earlier than the continuous part, raising the question: Is run time evaluation the right measure to analyze mixed-binary algorithms?