A unique quasi-one-dimensionally channeled nanomaze structure has been self-assembled in the (La0.7Sr0.3MnO3)1−x:(ZnO)x vertically aligned nanocomposites (VANs). Significantly enhanced magnetotransport properties have been achieved by tuning the ZnO composition x. The heteroepitaxial VAN thin films, free of large angle grain boundaries, exhibit a maximum low-field magnetoresistance (LFMR) of 75% (20 K and 1 T). The enhanced LFMR close to the percolation threshold is attributed to the spin-polarized tunneling through the ferromagnetic/insulating/ferromagnetic vertical sandwiches in the nanomazes. This study suggests that the phase boundary in the nanomaze structure is an alternative approach to produce decoupled ferromagnetic domains and thus to achieve enhanced magnetoresistance.