We perform a nonperturbative study of the electroweak phase transition (EWPT) in the two Higgs doublet model (2HDM) by deriving a dimensionally reduced high-temperature effective theory for the model, and matching to known results for the phase diagram of the effective theory. We find regions of the parameter space where the theory exhibits a first-order phase transition. In particular, our findings are consistent with previous perturbative results suggesting that the primary signature of a first-order EWPT in the 2HDM is $m_{A_0} > m_{H_0} + m_Z$.