Руска салата е неизоставен дел од празничната трпеза во регионов, но она што денес го јадеме нема многу допирни точки со оригиналниот рецепт, создаден во 1860-ите.

Нејзиното изворно име, кое и денес се користи во Русија, е Оливје салата, според белгискиот готвач Лусиен Оливје, кој бил шеф на кујната во „Ермитаж“, еден од најпознатите московски ресторани. Ја замислил како предјадење, при што измешал неколку специјалитети својствени за француската кујна и додал специјален прелив. Оваа салата станала заштитен знак на ресторанот, а оригиналниот рецепт, особено на прелиот, бил строго чувана тајна. Се верува дека рецептот варирал сезонски, а преливот на Оливје бил еден вид мајонез.

Оливје починал во 1883 година, а рецептот за неговата салата првпат бил отпечатен во 1894 и содржел месо од еребица, компир, марула, краставица, шкампи, капари, маслинки и неколку лажици мајонез. Познато е дека во неа претходно се ставале и кавијар и чадено месо од патка.

Овој скап и луксузен рецепт не ги преживеал револуционерните случувања во Русија во почетокот на 20. век и состојките подоцна биле заменети со далеку поевтини и подостапни. Руската салата преминала во советска варијанта, каква што до денес се прави во поранешна Југославија.