Sepsis is defined by life-threatening organ dysfunction during infection and is one of the leading causes of critical illness. During sepsis, there is high risk that new-onset of atrial fibrillation (AF) can occur, which is associated with significant morbidity and mortality. As a result, computer aided automated and reliable detection of new-onset AF during sepsis is crucial, especially for the critically ill patients in the intensive care unit (ICU). In this paper, a novel automated and robust two-step algorithm to detect AF from ICU patients using electrocardiogram (ECG) signals is presented. First, several statistical parameters including root mean square of successive differences, Shannon entropy, and sample entropy were calculated from the heart rate for the screening of possible AF segments. Next, Poincaré plot-based features along with P-wave characteristics were used to reduce false positive detection of AF, caused by the premature atrial and ventricular beats. A subset of the Medical Information Mart for Intensive Care (MIMIC) III database containing 198 subjects was used in this study. During the training and validation phases, both the simple thresholding as well as machine learning classifiers achieved very high segment-wise AF classification performance. Finally, we tested the performance of our proposed algorithm using two independent test data sets and compared the performance with two state-of-the-art methods. The algorithm achieved an overall 100% sensitivity, 98% specificity, 98.99% accuracy, 98% positive predictive value, and 100% negative predictive value on the subject-wise AF detection, thus showing the efficacy of our proposed algorithm in critically ill sepsis patients. The annotations of the data have been made publicly available for other investigators.