Drugie małżeństwo Romans Olgi z wielkim księciem Pawłem Aleksandrowiczem Romanowem spowodował ogromny skandal. Po śmierci pierwszej żony Pawła – wielkiej księżnej Aleksandry Greckiej, Olga została oficjalną kochanką Pawła. Miała z nim nawet syna – Włodzimierza Pawłowicza. Dopiero wtedy rozwiodła się z pierwszym mężem. Paweł poprosił o zgodę na ślub z Olgą, swojego bratanka – cara Mikołaja II, ale ten odmówił. W 1902 Paweł i Olga i tak się pobrali morganatycznie, ale z tego powodu Olga nie otrzymała tytułu wielkiej księżnej ani żadnego innego. W 1904 Luitpold, książę-regent Bawarii nadał Oldze tytuł hrabiny von Hohenfelsen. W 1913 Mikołaj II uznał małżeństwo Pawła i Olgi, i wezwał oboje do przeniesienia się do Petersburga (podobnie jak w przypadku morganatycznego małżeństwa swojego młodszego brata – Michała Romanowa z Natalią Szeremietjewską). Od Mikołaja II Olga otrzymała tytuł księżnej Paley.
Olga i Paweł mieli troje dzieci: księcia Włodzimierza Pawłowicza Paley (1897–1918), poetę, zamordowanego na Syberii razem z kilkoma kuzynami i ciotką Elżbietą Fiodorowną księżniczkę Irinę Pawłownę Paley (1903–1990), żonę: 1. księcia Fiodora Aleksandrowicza (syna Kseni Aleksandrowny), 2. Huberta Conquere, hrabiego de Monbrison księżniczkę Natalię Pawłownę Paley (1905–1981), żonę: 1. Luciena Lelonga, 2.