Andrássy Gyula gróf és Erzsébet osztrák császárné, magyar királyné között már az első találkozásuk alkalmával kölcsönös szimpátia alakult ki. Erre akkor került sor, amikor 1866. január 8-án Deák Ferenc javaslatára országgyűlési küldöttség utazott a királynő üdvözlésére Bécsbe.

Sissiről közismert, hogy fontosnak tartotta a tökéletes megjelenést, és nemcsak a saját, hanem mások vonatkozásában is, úgy is mondhatjuk, hogy szerette magát körülvenni szép emberekkel. Mivel Andrássy gróf jó képű és sármos férfinek számított, a karizmatikus személyiség mellett talán a vonzó külső is hozzájárulhatott a szimpátia kialakulásában. A baráti kapcsolat megerősödésében ugyanakkor legalább olyan hangsúlyos szerepet játszott, hogy mindketten az osztrákok és a magyarok közötti kiegyezés elkötelezett hívei voltak.

Erzsébet köztudomásúan szerette a magyarokat, melynek több oka is volt, így például az, hogy a fiatal császárné nem érezte jól magát a bécsi udvarban, sokkal szabadabb lehetett a gödöllői kastélyban, amit a magyaroktól kapott a koronázáskor ajándékba.

A királyné és a gróf Ferenczy Idán, Erzsébet társalkodónőjén keresztül folytatott levelezést egymással, amelynek során Andrássy így írta alá a leveleit: „Az Ön hű barátja”. A kapcsolatuk természetéről hamar pletykák terjedtek el, köztük még olyan spekuláció is megjelent, miszerint Mária Valériának valójában Andrássy az apja. A szigorú udvari etikett miatt azonban a királynénak és a grófnak még akkor sem lett volna módja a plátóinál szorosabb kapcsolatot létesíteni egymással, ha ilyen érzést egyáltalán tápláltak egymás iránt. Állítólag mindössze egyszer maradtak kettesben, 1872-ben, akkor is csupán néhány percre.

Andrássy Gyula halálakor Mária Valéria azt írta a naplójába, hogy édesanyja az egyetlen, igaz barátját gyászolja.