We investigate the associated production of charged Higgs bosons (H^pm) and W bosons at the CERN Large Hadron Collider, using the leptonic decay H^+ -> tau^+ nu_tau and hadronic W decay, within different scenarios of the Minimal Supersymmetric Standard Model (MSSM) with both real and complex parameters. Performing a parton level study we show how the irreducible Standard Model background from W + 2 jets can be controlled by applying appropriate cuts. In the standard m_h^max scenario we find a viable signal for large tan beta and intermediate H^pm masses (~ m_t). In MSSM scenarios with large mass-splittings among the heavy Higgs bosons the cross-section can be resonantly enhanced by factors up to one hundred, with a strong dependence on the CP-violating phases.