Relational reasoning is the ability to infer and understand the relations between multiple elements. In humans, this ability supports higher cognitive functions and is linked to fluid intelligence. Relational complexity (RC) is a cognitive framework that offers a generalisable method for classifying the complexity of reasoning problems. To date, increased RC has been linked to static patterns of brain activity supported by the frontoparietal system, but limited work has assessed the multivariate spatiotemporal dynamics that code for RC. To address this, we conducted representational similarity analysis in two independent neuroimaging datasets (Dataset 1 fMRI, n = 40; Dataset 2 EEG, n = 45), where brain activity was recorded while participants completed a visuospatial reasoning task that included different levels of RC (Latin Square Task). Our findings revealed that spatially, RC representations were widespread, peaking in brain networks associated with higher-order cognition (frontoparietal, dorsal-attention, and cingulo-opercular). Temporally, RC was represented in the 2.5-4.1 s post-stimuli window and emerged in the alpha and beta frequency range. Finally, multimodal fusion analysis demonstrated that shared variability within EEG-fMRI signals within higher-order cortical networks were better explained by the theorized RC model, relative to a model of cognitive effort (CE). Altogether, the results further our understanding of the neural representations supporting relational processing, highlight the spatially distributed coding of RC and CE across cortical networks, and emphasize the importance of late-stage, frequency-specific neural dynamics in resolving RC.