Ulan-Udè fou fundada el 1666 per cosacs russos. A causa de la seva situació geogràfica la ciutat va créixer ràpidament i es va convertir en un gran centre comercial que connectava Rússia amb la Xina i Mongòlia.
De l'època de la fundació provenen les antigues mansions dels comerciants, ricament decorades amb fusta i pedra tallada, que encara es conserven al centre d'Ulan-Udè, a la vora del riu. Aquestes cases són un bell exemple del classicisme rus. A la plaça major hi destaca un gran cap de Lenin, monument actualment poc habitual en terres russes.