The dielectric, magnetic, and magnetodielectric properties of Ca2FeAO5+δ (A = Al, Ga) ceramics were investigated together with their crystal structures. Rietveld refinement of the X-ray diffraction data indicated that the space group of the Ca2FeAlO5+δ ceramic was Ibm2, whereas that of the Ca2FeGaO5+δ ceramic was Pcmn. Dielectric relaxation above room temperature, originating from the Maxwell–Wagner effect and polaronic hole hopping between Fe3+ and Fe4+ ions, was observed in both ceramics. Weak ferrimagnetic behavior was identified from the magnetic-field-dependent magnetization in these ceramics, which was attributed to the non-cancelled spins of the antiferromagnetic-ordered Fe3+ and Fe4+ ions. An intrinsic, giant, room-temperature magnetodielectric coefficient of up to −23.3% was achieved in the Ca2FeAlO5+δ ceramic at 50 MHz, which was attributed to the suppression of charge fluctuations of Fe3+ and Fe4+ ions in the magnetic field.