Bratu oteo nevestu
Njen otac je bio ruski pukovnik Jovan Keško, sa posedom u Besarabiji, a majka Rumunka, u rodu sa mnogim uglednim moldavskim porodicama. Ako i nije bila ruska princeza, Natalija je upola bila Ruskinja, što je delimično zadovoljilo zahteve srpskog kneza. Iako se braku vladara do tog trenutka poklanjala ogromna pažnja, ženidba Natalijom uopšte nije bila pripremana. Pretpostavlja se da je presudila Marija, kneževa majka, savetom sinu da baš ovu devojku uzme za ženu.
Knez je sa svojim bogatim bratom od tetke Aleksandrom Konstatinovićem pošao u Beč. Aleksandrova namera je bila da se upozna sa Natalijom, a ne Milanova. Ali, čim je video Nataliju, knez je bio hitriji od svog rođaka i, što je bilo uobičajeno za njega, odmah se zaljubio i brže-bolje je isprosio.
Natalija je sva srećna odmah pristala, uverena da joj se ispunjava proročanstvo jedne Ciganke, koja joj je rekla da će biti ne samo kneginja, nego i kraljica.
"Sanjala sam čaroban san i bila sam vrlo zaljubljena u svog verenika", zapisala je ona, iako se sa srpskim knezom viđala samo deset dana.
Sve se odigravalo kao u nekakvom ljubavnom romanu. Knez je srpske državnike, koji su noge podbili provodadžišući za njega, stavio pred svršen čin - obavestio ih je proševini samo jednim telegramom! Verio se sa Natalijom u Beču, a venčali su se u Sabornoj crkvi u Beogradu 17. oktobra 1875. godine.
Pre toga je Natalija provela samo jedan dan u Beogradu, na jednom proputovanju iz Beča za Rumuniju. Beograđani su oduševljeno dočekali kneževu verenicu, pet godina mlađu od kneza. A ona je odmah odlučila da postane prava Srpkinja: dvor je odmah uposlio čuvenog srpskog jezikoslovca Đuru Daničića da kneginji daje časove srpskog jezika.