Atomic layer deposition (ALD) was used to modify two different types of carbon black-based Pt oxygen reduction catalysts with protective TiO2 nanostructures to increase catalyst durability. Rates of ALD growth and the structure of deposited TiO2 were observed to be highly dependent on oxygen content of the catalyst substrate. Electrochemical durability was enhanced with the addition of TiO2 ALD nanostructures, with up to 70% retention in mass activity measured over accelerated durability testing. High-temperature treatment of the top-performing ALD catalyst, which was found to promote structural rearrangement of the TiO2 and Pt phases into hybrid nanoparticles, yielded a twofold increase in activity but was detrimental to durability.