Spinodal decomposition is a ubiquitous phenomenon leading to phase separation from a uniform solution. We show that a spinodal decomposition occurs in a unique combination of two rutile compounds of TiO2 and VO2, which are chemically and physically distinguished from each other: TiO2 is a wide-gap insulator with photo catalytic activities and VO2 is assumed to be a strongly correlated electron system which exhibits a dramatic metal-insulator transition at 342 K. The spinodal decomposition takes place below 830 K at a critical composition of 34 mol% Ti, generates a unidirectional composition modulation along the c axis with a wavelength of approximately 6 nm, and finally results in the formation of self-assembled lamella structures made up of Ti-rich and V-rich layers stacked alternately with 30-50 nm wavelengths. A metal-insulator transition is not observed in quenched solid solutions with intermediate compositions but emerges in the thin V-rich layers as the result of phase separation. Interestingly, the metal-insulator transition remains as sharp as in pure VO2 even in such thin layers and takes place at significantly reduced temperatures of 310-340 K, which is probably due to a large misfit strain induced by lattice matching at the coherent interface.