EEG-correlated fMRI analysis is widely used to detect regional BOLD fluctuations that are synchronized to interictal epileptic discharges, which can provide evidence for localizing the ictal onset zone. However, the typical, asymmetrical and mass-univariate approach cannot capture the inherent, higher order structure in the EEG data, nor multivariate relations in the fMRI data, and it is nontrivial to accurately handle varying neurovascular coupling over patients and brain regions. We aim to overcome these drawbacks in a data-driven manner by means of a novel structured matrix-tensor factorization: the single-subject EEG data (represented as a third-order spectrogram tensor) and fMRI data (represented as a spatiotemporal BOLD signal matrix) are jointly decomposed into a superposition of several sources, characterized by space-time-frequency profiles. In the shared temporal mode, Toeplitz-structured factors account for a spatially specific, neurovascular ‘bridge’ between the EEG and fMRI temporal fluctuations, capturing the hemodynamic response's variability over brain regions. By analyzing interictal data from twelve patients, we show that the extracted source signatures provide a sensitive localization of the ictal onset zone (10/12). Moreover, complementary parts of the IOZ can be uncovered by inspecting those regions with the most deviant neurovascular coupling, as quantified by two entropy-like metrics of the hemodynamic response function waveforms (9/12). Hence, this multivariate, multimodal factorization provides two useful sets of EEG-fMRI biomarkers, which can assist the presurgical evaluation of epilepsy. We make all code required to perform the computations available at https://github.com/svaneynd/structured-cmtf.