Nonstoichiometric perovskite-related oxides (e.g. ferrites and cobaltites, etc.) are characterized by fast oxygen transport at ambient temperatures, which relates to the microstructural texturing of these materials, consisting wholly of nanoscale microdomains. We have developed a heterogeneous diffusion model to describe the kinetics of oxygen incorporation into nanostructured oxides. Nanodomain boundaries are assumed to be the high diffusivity paths for oxygen transport whereas diffusion into the ordered domains proceeds much slower. The model has been applied for qualitative evaluation of oxygen diffusion parameters from the data on wet electrochemical oxidation of nanostructured perovskite SrCo0.5Fe0.2Ta0.3O3−y samples. Using Laplace transform methods, an exact solution is found for a ramped step-wise potential, allowing fitting of the experimental data to theoretical curves (in Laplace transforms). A further model generalization is considered by introducing additional parameters for the size distribution of domains and particles.