Reduced titanium oxide structures are regarded as promising materials for various catalytic and optoelectronic applications. There is thus an urgent need for developing methods of controllable formation of crystalline nanostructures with tunable oxygen nonstoichiometry. We introduce the Extremely Low Oxygen Partial Pressure (ELOP) method, employing an oxygen getter in close vicinity to an oxide during thermal reduction under vacuum, as an effective bottom-up method for the production of nanowires arranged in a nanoscale metallic network on a SrTiO3 perovskite surface. We demonstrate that the TiO nanowires crystallize in a highly ordered cubic phase, where single nanowires are aligned along the main crystallographic directions of the SrTiO3 substrate. The dimensions of the nanostructures are easily tunable from single nanometers up to the mesoscopic range by varying the temperature of reduction. The interface between TiO and SrTiO3 (metal and insulator) was found to be atomically sharp providing the unique possibility of the investigation of electronic states, especially since the high conductivity of the TiO nanostructures is maintained after room temperature oxidation. According to the growth model we propose, TiO nanowire formation is possible due to the incongruent sublimation of strontium and crystallographic shearing, triggered by the extremely low oxygen partial pressure (ELOP). The controlled formation of conductive nanowires on a perovskite surface holds technological potential for implementation in memristive devices, organic electronics, or for catalytic applications, and provides insight into the mechanism of nanoscale phase transformations in metal oxides. We believe that the ELOP mechanism of suboxide formation is suitable for the formation of reduced suboxides on other perovskite oxides and for the broader class of transition metal oxides.