Recent experiments on Coulomb drag in the quantum Hall regime have yielded a number of surprises. The most striking observations are that the Coulomb drag can become negative in high Landau levels and that its temperature dependence is non-monotonous. We develop a systematic diagrammatic theory of Coulomb drag in strong magnetic fields explaining these puzzling experiments. The theory is applicable both in the diffusive and the ballistic regimes; we focus on the experimentally relevant ballistic regime (interlayer distance $a$ smaller than the cyclotron radius $R_c$). It is shown that the drag at strong magnetic fields is an interplay of two contributions arising from different sources of particle-hole asymmetry, namely the curvature of the zero-field electron dispersion and the particle-hole asymmetry associated with Landau quantization. The former contribution is positive and governs the high-temperature increase in the drag resistivity. On the other hand, the latter one, which is dominant at low $T$, has an oscillatory sign (depending on the difference in filling factors of the two layers) and gives rise to a sharp peak in the temperature dependence at $T$ of the order of the Landau level width.