De Heer od początku wiedział, że "Tajemnica Aleksandry" będzie intensywnym, wycieńczającym emocjonalnie przeżyciem dla wszystkich zainteresowanych, zwłaszcza dla dwójki aktorów pierwszoplanowych.
Rolę męża, Steve’a, de Heer zaczął pisać z myślą o Garym Sweecie, gdy "The Tracker" wchodził w fazę post-produkcji.
Reżyser wspomina: "Bardzo miło współpracowało mi się z nim w The Tracker, lecz wiedziałem, że będzie to trudna rola. Zadzwoniłem do niego i powiedziałem: Gary, napiszę dla ciebie rolę, ale muszę cię ostrzec, że nie będzie jej łatwo zagrać. Będzie zupełnie różna od tego, co dotychczas grałeś. A Gary, w swoim niemożliwym do podrobienia stylu, odpowiedział po prostu: Leć na całego, stary. I tak zrobiłem".
"Jest w publicznym wizerunku Gary’ego i w jego doświadczeniu aktorskim coś, co czyni go idealnym do tej roli" - zauważa de Heer. "Jest postrzegany w określony sposób, bo był wiele razy żonaty i zawsze coś o nim piszą w brukowcach. To według mnie bardzo pasowało do kogoś, kto miał grać Steve’a".
Gary mile wspomina ofertę de Heera: "Gra w The Tracker była wspaniałym doświadczeniem aktorskim i utwierdziła mnie w opinii, że chcę współpracować z Rolfem kiedy tylko się da, bo jest niezwykle inteligentnym, wrażliwym i zabawnym facetem". Po czym dodaje żartobliwie: "Reżyser też z niego niezgorszy".
De Heer zaczął pisać "Tajemnicę Aleksandry" konkretnie dla Gary’ego Sweeta, jednak nie wiedział jeszcze, kogo zaangażować do roli Aleksandry, a podjęcie właściwego wyboru mogło stanowić pewien problem. Wiedział, że musi znaleźć kogoś niezwykle wszechstronnego, utalentowanego i odważnego, kto byłby w stanie podołać tej złożonej, dosadnej kreacji.
"Gdy scenariusz był już gotowy, powędrował do paru utalentowanych aktorek, które według mnie nadawały się do tej roli. Dwie lub trzy z nich naprawdę z ogromnym żalem odmówiły. Wszystkie bardzo chciały się tego podjąć, bo była to bardzo interesująca, oferująca wiele wyzwań rola. Jednak jednocześnie czuły, że nie nadawały się do tego lub nie chciały tego zrobić z powodów osobistych, bo mogłoby to na przykład źle wpłynąć na ich dzieci" - dodaje de Heer.
Przed pokazem "The Tracker" na Adelaide Festival of Arts w lutym 2002 roku, de Heer i Julie Ryan rozpoczęli wstępne prace nad "Tajemnicą Aleksandry", mimo że jedna z głównych ról nie była jeszcze obsadzona. Postanowili zatrudnić do pomocy Faith Martin, specjalistkę do spraw castingów z Sydney.
"Faith zgromadziła w Sydney i Melbourne wielu bardzo interesujących ludzi" - wspomina de Heer. "Tak się złożyło, ze w tym samym czasie w Sydney był Gary. Przyszedł więc na parę castingów, by mi towarzyszyć. W końcu zgodziliśmy się, że Helen Buday ma największe szanse sprawdzić się w roli żony. Ma tą tajemniczą, ukrytą wyrazistość. Wprowadziła do tej roli emocjonalną głębię, która idealnie współgrała z moją wizją Aleksandry".
Helen Buday ochoczo skorzystała z okazji, by ponownie zagrać w filmie Rolfa - wcześniej pracowała z nim w 1990 roku, podczas realizacji "Dingo".
"Kręcenie Dingo było wspaniałym przeżyciem. Choć jestem głównie aktorką teatralną, to uważam pracę z Rolfem za czystą rozkosz. Pozwala ci na siebie. Pozwala ci wnieść do danej roli to, co tylko chcesz i uwzględnia te dodatkowe aspekty, a to rzadko spotykane. Uzyskujesz coś, czego on się nie spodziewał, czego samemu się nie spodziewałeś, a całość tworzycie razem. Po prostu rzuciłam się w ten projekt. To film bez precedensu, nie widziałam nigdy niczego podobnego" - dodaje Helen.
Dwie główne role były obsadzone, pozostawała tylko postać Billa, sąsiada z zacięciem do systemów bezpieczeństwa.
Rolf uważał, że Bill powinien być bardziej światowy niż Steve, miał to być człowiek kulturalny, przeciwwaga dla podmiejskiej mentalności głównego bohatera: "Myślałem o jakimś imigrancie, lecz nie byłem pewien, czy to ma być Turek, Grek, czy Bułgar. Po prostu wiedziałem, że musi to być ktoś bardzo różniący się od Steve’a, z innymi doświadczeniami w życiu i małżeństwie".
Rolf przypomniał sobie aktora, którego widział w eksperymentalnej sztuce w Sydney, jakieś dwadzieścia lat wcześniej. Według niego idealnie nadawałby się do tej roli: "Pamiętam, że gdy jeszcze mieszkałem w Sydney, zobaczyłem bardzo ciekawego, polskiego aktora, który nazywał się Bogdan Koca. Był bardzo dobry, mimo że jego rola nie była zbyt wyeksponowana. Bardzo mi się spodobał. Dlatego też, gdy wyłowiłem w Sydney Helen, zaaranżowałem jednocześnie spotkanie z Bogdanem. Mimo upływu dwudziestu lat nadal wydawał mi się niezwykle interesujący, więc dalej już nie szukałem".
Podobnie jak Helen Buday, Bogdan Koca był niezwykle podniecony możliwością współpracy z de Heerem. "Gdy Rolf mnie spytał, czy jestem zainteresowany rolą Billa, powiedziałem coś w stylu: Nie chcę nawet czytać scenariusza, zrobię wszystko byle z tobą pracować, choćbyś miał nakręcić książkę telefoniczną. Jestem zafascynowany twoim kreatywnym podejściem do tworzenia filmów".
W porównaniu do ról Steve’a i Aleksandry, partia Billa mogła się wydawać skromna, lecz Koca zdawał sobie sprawę, że była ona ważnym elementem dramatu: "Uważam Billa za niezwykłą postać. Najbardziej w tym filmie mnie zaciekawiło to, że życie Billa jest równoległym przełożeniem uczuciowego życia Steve’a, męskiej ofiary tej historii. To jakby lustrzane odbicia. Niemałym wyzwaniem było dla mnie, jako aktora, opowiedzenie historii tego człowieka za pomocą zaledwie paru kwestii i drobnych epizodów".
