Crystallinity and conductivity results for a new nanocomposite PEO:LiClO4 with nano-sized Fe3O4 particles are presented in this paper. The DSC measurements have shown a decrease in the degree of crystallinity of PEO by the inclusion of LiClO4 salt and further decrease with the addition of Fe3O4 nanoparticles. The nano-sized Fe3O4 surface has a Lewis acidic group capable of interaction with Lewis base centers of the polymer PEO chain in the nanocomposite electrolyte, resulting in decrease in PEO crystallinity and enhancement of miscibility in the presence of LiClO4 salt. Annealed at 125 °C of the PEO:LiClO4 electrolyte shows melting endotherm at 175 °C, but this endotherm is absent with the incorporation of nano-sized Fe oxide particles. This electrolyte system has a one and a half order of magnitude higher ionic conductivity compared to a standard PEO:LiClO4 electrolyte. Optimized conductivity is found at a 10 wt.% Fe3O4 composition while above this concentration, the conductivity is decreased due to aggregation of a Fe3O4:Li rich phase.