Electroencephalography (EEG) signals recorded during simultaneous functional magnetic resonance imaging (fMRI) are contaminated by strong artifacts. Among these, the ballistocardiographic (BCG) artifact is the most challenging, due to its complex spatio-temporal dynamics associated with ongoing cardiac activity. The presence of BCG residuals in EEG data may hide true, or generate spurious correlations between EEG and fMRI time-courses. Here, we propose an adaptive Optimal Basis Set (aOBS) method for BCG artifact removal. Our method is adaptive, as it can estimate the delay between cardiac activity and BCG occurrence on a beat-to-beat basis. The effective creation of an optimal basis set by principal component analysis (PCA) is therefore ensured by a more accurate alignment of BCG occurrences. Furthermore, aOBS can automatically estimate which components produced by PCA are likely to be BCG artifact-related and therefore need to be removed. The aOBS performance was evaluated on high-density EEG data acquired with simultaneous fMRI in healthy subjects during visual stimulation. As aOBS enables effective reduction of BCG residuals while preserving brain signals, we suggest it may find wide application in simultaneous EEG-fMRI studies.