This paper introduces an automated methodology for the extraction of fetal heart rate from cutaneous potential abdominal electrocardiogram (abdECG) recordings. A three-stage methodology is proposed. Having the initial recording, which consists of a small number of abdECG leads in the first stage, the maternal R-peaks and fiducial points (QRS onset and offset) are detected using time-frequency (t-f) analysis and medical knowledge. Then, the maternal QRS complexes are eliminated. In the second stage, the positions of the candidate fetal R-peaks are located using complex wavelets and matching theory techniques. In the third stage, the fetal R-peaks, which overlap with the maternal QRS complexes (eliminated in the first stage) are found using two approaches: a heuristic algorithm technique and a histogram-based technique. The fetal R-peaks detected are used to calculate the fetal heart rate. The methodology is validated using a dataset of eight short and ten long-duration recordings, obtained between the 20th and the 41st week of gestation, and the obtained accuracy is 97.47%. The proposed methodology is advantageous, since it is based on the analysis of few abdominal leads in contrast to other proposed methods, which need a large number of leads.