Magnetoelectric barium titanate ceramics with embedded cobalt iron alloy particles (Co1/3Fe2/3)(x)-(BaTiO3)((1-x)), with x=0.2, 0.4, and 0.6, were prepared by a polyol-mediated synthesis with subsequent sintering in a reducing forming gas atmosphere. The samples were characterized by XRD and SEM/EDX measurements. The sizes of the Co1/3Fe2/3 grains increase with x. Impedance spectroscopy showed a behavior similar to pure BaTiO3, in particular the occurrence of the ferroelectric-paraelectric phase transition, and high permittivities for the sample with x=0.6, that is, near the percolation threshold. The samples exhibit soft ferromagnetic properties with large saturation magnetizations of 2.5 (B)/atom and narrow hystereses. Detailed magnetoelectric investigations revealed a unique DC-field dependence of (ME) for all three compositions. Most remarkably, the sample with x=0.4 possesses a broad ME hysteresis and an inversion of the sign of (ME) at 5 kOe.