PdO-doped $BaZr_{0.85}Y_{0.15}O_{3-delta}$ (BZPY) proton conductors have been proposed as applicable for intermediate temperature electrolytes for protonic ceramic fuel cells (PCFCs) because the PdO doping is effective for improving the proton conductivity of $BaZr_{0.85}Y_{0.15}O_{3-delta}$ (BZY) with high affinity for hydrogen. In order to further improve the conductivity of BZPY, two-phase composite electrolytes consisting of a BZPY and molten carbonate were designed. Dense BZPY-based composite electrolytes were fabricated after sintering at $670^{circ}C$ for 4 h, since molten carbonates fill the grain boundary of the porous BZPY matrix. Furthermore, BZPY/$(Li-0.5Na)_2CO_3$ composites show a significantly enhanced protonic conductivity at intermediate temperatures. This may be because easy proton transport is possible through the interface of the carbonate and oxide phase.