Self-assembled platinum and gold nanostructures, which are formed by evaporation and subsequent diffusion limited aggregation of metal on highly oriented pyrolytic graphite, have been studied by photoemission spectroscopy and scanning electron microscopy. Dendritic gold nanostructures were observed on samples onto which gold was evaporated at room temperature. For samples onto which gold was evaporated at reduced temperatures, no such dendrites were found. For samples evaporated with platinum, small nano-spiders were seen at low evaporation time, and more complex fractal structures at higher evaporation time. Studying the oxidation of carbon monoxide over the platinum nanostructures yielded no clear corrolation between nanostructure size and oxidation rate.