(Ni/Cu, Ti)-YSZ samples were synthesized by self-assembling synthesis route using Triton X as template and thermal treated at 700 °C and 900 °C in air flow. Microstructure, surface chemistry and electrochemical properties were assessed by XRD, N2 adsorption-desorption, SEM, TEM, XPS, TPR-H2 and DC conductivity measurements. The synthesis route leads to a very well incorporation of Ti into YSZ lattice. X-ray diffraction shows that (Cu, Ti)-YSZ exhibits a phase transition, from cubic fluorite phase to monoclinic, when the calcination temperature rises from 700 °C to 900 °C, while (Ni, Ti)-YSZ exhibits only two cubic phases, with a main fluorite-type phase and a secondary isostructural phase with bunsenite (NiO) for both calcination temperatures. The partial oxidation of methane was performed in the temperature range 250–900 °C, and the results can be summarized as follows: i) for the (Cu, Ti)-YSZ samples it was found that the phase transformation from cubic fluorite to monoclinic favors an increase in methane conversion as well as the selectivity to CO; ii) the samples containing Ni are more active than those containing Cu, with 90% methane conversion at 750 °C as compared to 75% conversion, respectively. Regarding the total conductivity of the material synthesized, two different behaviors were obtained depending on the composition; the (Ni, Ti-)YSZ maintained a prevailing ionic conductivity, whereas the (Cu, Ti)-YSZ exhibited mainly n-type conductivity. The ionic conductivity of Ni-based sample is beneficial for the partial oxidation of methane due to the oxygen vacancies generated on the surface of the material, which plays a fundamental role in the O2 activation mechanism and is in accordance with higher catalytic activity observed for the Ni containing sample.