[[Bestand:Mariya Nikolayevna i Olga Nikolayevna.jpg|thumb|250px|Grootvorstin Olga samen met haar oudere zuster grootvorstin Maria]]
Olga ontmoette kroonprins [[Karel I van Württemberg|Karel van Württemberg]] in het begin van [[1846]] in [[Palermo (stad)|Palermo]] stad in het [[Koninkrijk der Beide Siciliën]]. Het was de wens van haar ouders dat er een huwelijk tussen de beide families tot stand kwam, vooral omdat haar broer Alexander en haar zussen Maria en Alexandra niet bepaald waren getrouwd met vooraanstaande families in Europa. Er warenhadden al eerder huwelijken plaatsgevonden tussen leden van de Russische Keizerlijke familie en de Württembergse Koninklijke familie. Olga's toekomstige schoonvader was getrouwd met grootvorstin [[Catharina Paulowna van Rusland|Catharina Paulowna]], een tante van Olga. En eenEen oom van Olga, grootvorst [[Michaël Pavlovitsj van Rusland|Michaël Pavlovitsj]], was gehuwd met prinses [[Helena Charlotte van Württemberg]]. En deDe vrouw van tsaar Paul I was prinses Sophia Dorothea van Württemberg.
Olga gaf al toestemming voor een huwelijk nadat ze Karel nog maar een paar keer had gezien. De verloving werd op [[18 januari]] [[1846]] bekendgemaakt. De trouwdag was op [[13 juli]] 1846 en werd groots gevierd in het [[Paleizencomplex in Peterhof]] in Rusland. Het koppel reisde van Rusland naar Württemberg en ze kwamen daar aan op [[23 september]]. Ze woonden de meeste tijd in Villa Berg in [[Stuttgart]] en in het Kloster Hofen in Friedrichshafen.
Het koppel kreeg geen kinderen, dit komt waarschijnlijk door de [[Homoseksualiteit|homoseksuele]] geaardheid van Karel. Olga's echtgenoot werd het mikpunt van schandaal door zijn verbondenheid met verschillende mannen. De meest bekende van deze mannen was de [[Verenigde Staten|Amerikaan]] Charles Woodcock, een voormalige kamerheer van Karel. Karel had hem in [[1888]] verheven tot Baronbaron. Dit resulterendeleidde in eentot groot protest en uiteindelijk moest Karel afstand doen van zijn favoriete kamerheer. In [[1863]] adopteerden Olga en Karel een nichtje van Olga, grootvorstin [[Vera Konstantinova van Rusland (1854-1912)|Vera Konstantinova van Rusland]], een dochter van Olga's broer, grootvorst [[Constantijn Nikolajevitsj van Rusland|Constantijn]].
Op [[25 juni]] [[1864]], na de dood van koning Willem I, besteeg Karel de troon en werd hij de derde koning Württemberg, daardoor werden Olga de vierde koningin van Württemberg. De nieuwe koning werd op [[12 juli]] 1864 gekroond.