The role of ruthenium and its oxides in catalysis, electrochemistry, and electronics is becoming increasingly important because of the high thermal and chemical stability, low resistivity, and unique redox properties of this metallic system. We report an observation of RuO2 nanorods decorated with nanometer size Ru metal clusters. We identify precise crystallographic relationships between metal and oxide, and provide a simple model for the synthesis of these structures, based on the theory of columnar growth. The high aspect ratio, high surface area, and quantum size crystalline decorations of these nanostructures make them particularly attractive candidates for further fundamental research and for advanced catalytic and electronic applications.