The magnesium conducting solid-state polymer electrolyte PE comprising hybrid of poly(vinyl alcohol) (PVA) and magnesium bromide MgBr2, phosphomolbidic acid (PMA) H3PMo12O40, and tetraethylene glycol dimethyl ether (TEGDME) as plasticizer and TiO2 anatase as a nano-filler is prepared at various compositions by solution cast technique. The interactions between the filler and PE chains are studied by thermal gravimetric analysis (TGA), X-ray diffraction (XRD), scanning electron microscopy (SEM), and impedance spectroscopy. Composition of PE is optimized, and maximum conductivity is obtained at 6 wt.% TiO2 anatase. Filler seems to increase the number of free magnesium cations by de-coordinating the bond between magnesium cations and matrix scheme. The estimated value of Mg+ ion transference number is carried out by the combination of complex impedance and D.C. polarization methods and is found to be 0.52 for the highest conducting film. A solid state battery based on the above polymer electrolyte with a configuration Mg|PE|TiO2 has exhibited a discharge capacity > 8.5 mAh/gm. The discharge characteristics are found to be satisfactory as a laboratory cell.