In this study, an effective methodology for segmenting the temporal trace of phonocardiographic signals (PCG) is presented. Initially, inter-beat segmentation is carried out using the DII lead of the ECG recording for locating the occurrence of the first heart sound (S1). Next, the intra-beat segmentation is achieved by using recurrence time statistics (RTS), which is sensitive to changes of the reconstructed attractor in a state space derived from nonlinear dynamic analysis. If the segmentation using RTS fails, an alternative segmentation is proposed using thresholding over the Shannon envelogram extracted from the high-frequency decomposition. The database of PCG records which was used belongs to the National University of Colombia. Inter-beat segmentation accuracy was 100% over all PCG recordings. Taking into account 360 PCG beats, where a set of 180 beats were strongly disturbed by different types of cardiac murmurs, intra-beat segmentation yielded an accuracy result of 97.7%.