We investigate the strength of the electroweak phase transition (EWPT) within the CP-violating 2-Higgs-Doublet Model (C2HDM). The 2HDM is a simple and well-studied model, which can feature CP violation at tree level in its extended scalar sector. This makes it, in contrast to the Standard Model (SM), a promising candidate for explaining the baryon asymmetry of the universe through electroweak baryogenesis. We apply a renormalisation scheme which allows efficient scans of the C2HDM parameter space by using the loop-corrected masses and mixing matrix as input parameters. This procedure enables us to investigate the possibility of a strong first order EWPT required for baryogenesis and study its phenomenological implications for the LHC. Like in the CP-conserving (real) 2HDM (R2HDM) we find that a strong EWPT favours mass gaps between the non-SM-like Higgs bosons. These lead to prominent final states comprised of gauge+Higgs bosons or pairs of Higgs bosons. In contrast to the R2HDM, the CP-mixing of the C2HDM also favours approximately mass degenerate spectra with dominant decays into SM particles. The requirement of a strong EWPT furt ... mehrher allows us to distinguish the C2HDM from the R2HDM using the signal strengths of the SM-like Higgs boson. We additionally find that a strong EWPT requires an enhancement of the SM-like trilinear Higgs coupling at next-to-leading order (NLO) by up to a factor of 2.4 compared to the NLO SM coupling, establishing another link between cosmology and collider phenomenology. We provide several C2HDM benchmark scenarios compatible with a strong EWPT and all experimental and theoretical constraints. We include the dominant branching ratios of the non-SM-like Higgs bosons as well as the Higgs pair production cross section of the SM-like Higgs boson for every benchmark point. The pair production cross sections can be substantially enhanced compared to the SM and could be observable at the high-luminosity LHC, allowing access to the trilinear Higgs couplings.