Atrial Fibrillation (AF) is a serious cardiovascular condition that can lead to complications, including but not limited to stroke, heart attack, and death. AF can be diagnosed using an electrocardiogram (ECG); however, continuous monitoring produces a large amount of data that can increase storage, power, and transmission bandwidth requirements. Compressive sensing has been used to mitigate increased requirements of continuous monitoring. An AF detector using a deterministic compressively sensed ECG is proposed. By detecting AF in the compressed domain, the computationally expensive process of reconstructing the ECG can be avoided. The detector was based on a random forest trained on features extracted using the wavelet transform, empirical mode decomposition, discrete cosine transform, and statistical methods. ECG data from the Long-Term Atrial Fibrillation Database available on Physionet were used. The performances of the detectors trained using features from compressed and uncompressed ECG were compared. Using the trained detector, the area under the receiver operating curve (AUC) and the weighted average precision (AP) were both 0.93 for uncompressed data using record-based 10-fold cross-validation. The AUC and AP were 0.91 and 0.90 at 50% compression, 0.92 and 0.91 at 75% compression, and 0.82 and 0.91 at 95% compression, respectively.