Electrophysiological monitoring of the fetal-heart and the uterine-muscle activity, referred to as an electrohysterogram, is essential to permit timely treatment during pregnancy. While remarkable progress is reported for fetal-cardiac-activity monitoring, the electrohysterographic (EHG) measurement and interpretation remain challenging. In particular, little attention has been paid to the analysis of the EHG propagation, whose characteristics might be predictive of the preterm delivery. Therefore, this paper focuses, for the first time, on the noninvasive estimation of the conduction velocity of the EHG-action potentials. To this end, multichannel EHG recording and surface high-density electrodes are used. A maximum-likelihood method is employed for analyzing the EHG-action-potential propagation in two dimensions. The use of different weighting strategies of the derived cost function is introduced to deal with the poor signal similarity between different channels. The presented methods were evaluated by specific simulations proving the best weighting strategy to lead to an accuracy improvement of 56.7%. EHG measurements on ten women with uterine contractions confirmed the feasibility of the method by leading to conduction velocity values within the expected physiological range.