L'ouverture de la rue est faite par décret municipal du , après le réaménagement de l'ancienne « cité d'Odessa » créée durant la guerre de Crimée.
Bâtiments remarquables et lieux de mémoire
Le bas de la rue d'Odessa était le site de l'ancienne gare de Paris-Montparnasse au début du XXe siècle. Elle est aujourd'hui connue comme étant une rue où se trouvent de très nombreuses crêperies bretonnes, en raison de la communauté qui s'était installée à la fin du XIXe siècle dans le quartier du Montparnasse.
No 5 : bains d'Odessa ; la façade sur cour avec son décor en céramique est inscrite aux monuments historiques en 1983[4].
No 13 : emplacement de l'enseigne du Chat Blanc[5].
Nos 16-18 : le cinéma Les Montparnos se trouve à cet emplacement depuis 1981.
Nos 16 : deux appartements sont la propriété de la SCI Sadryna fondée en 2007, dont le gérant est Tahar El-Materi, proche de l'ancien président tunisien Zine el-Abidine Ben Ali, et oncle de Mohamed Sakhr El Materi, gendre de ce dernier[6].
No 18 : emplacement de l'atelier et académie du peintre André Lhote, fondée en 1922[7], où s'installa plus tard le peintre Henri Goetz jusqu'à la démolition en 1974-1975[réf. nécessaire].
No 28 : hôtel Odessa, où vécurent et travaillèrent :