Imaging the bio-impedance distribution of the brain can provide initial diagnosis of acute stroke. This paper presents a compact and non-radiative tomographic modality, i.e. multi-frequency Electromagnetic Tomography (mfEMT), for the initial diagnosis of acute stroke. The mfEMT system consists of 12 channels of gradiometer coils with adjustable sensitivity and excitation frequency. To solve the image reconstruction problem of mfEMT, we propose an enhanced Frequency-Constrained Sparse Bayesian Learning (FC-SBL) to simultaneously reconstruct the conductivity distribution at all frequencies. Based on the Multiple Measurement Vector (MMV) model in the Sparse Bayesian Learning (SBL) framework, FC-SBL can recover the underlying distribution pattern of conductivity among multiple images by exploiting the frequency constraint information. A realistic 3D head model was established to simulate stroke detection scenarios, showing the capability of mfEMT to penetrate the highly resistive skull and improved image quality with FC-SBL. Both simulations and experiments showed that the proposed FC-SBL method is robust to noisy data for image reconstruction problems of mfEMT compared to the single measurement vector model, which is promising to detect acute strokes in the brain region with enhanced spatial resolution and in a baseline-free manner.