Patient-ventilator asynchronies can be detected by close monitoring of ventilator screens by clinicians or through automated algorithms. However, detecting complex patient-ventilator interactions (CP-VI), consisting of changes in the respiratory rate and/or clusters of asynchronies, is a challenge. Sample Entropy (SE) of airway flow (SE-Flow) and airway pressure (SE-Paw) waveforms obtained from 27 critically ill patients was used to develop and validate an automated algorithm for detecting CP-VI. The algorithm’s performance was compared versus the gold standard (the ventilator’s waveform recordings for CP-VI were scored visually by three experts; Fleiss’ kappa = 0.90 (0.87–0.93)). A repeated holdout cross-validation procedure using the Matthews correlation coefficient (MCC) as a measure of effectiveness was used for optimization of different combinations of SE settings (embedding dimension, m, and tolerance value, r), derived SE features (mean and maximum values), and the thresholds of change (Th) from patient’s own baseline SE value. The most accurate results were obtained using the maximum values of SE-Flow (m = 2, r = 0.2, Th = 25%) and SE-Paw (m = 4, r = 0.2, Th = 30%) which report MCCs of 0.85 (0.78–0.86) and 0.78 (0.78–0.85), and accuracies of 0.93 (0.89–0.93) and 0.89 (0.89–0.93), respectively. This approach promises an improvement in the accurate detection of CP-VI, and future study of their clinical implications.