"Dziękuję Panu, iż nalegał Pan, że Melania była piękna. Przedstawiłam ją jako małą, skromną osóbkę, ale w moim sercu również uważałam ją za piękną." - Margaret Mitchell do Roberta W. Binghama 23 lutego 1937 "Dałbym wszystko by mieć Olivię de Havilland..." - D. Selznick w liście do Daniela T. O'Shea, vice prezesa Selznick International 18 listopada 1938

Poszukiwanie aktorki do roli Meli było równie żmudne. Trzeba było znaleźć aktorkę, która potrafiła by oddać złożoność charakteru Melanii: ukazać jej życzliwość, jej wewnętrzną siłę, jej prostolinijność i jej dojrzałość. 

Cukor używał scenę rozmowy Scarlett i Melanii do zdjęć próbnych; scenę która nie została uwzględniona w końcowej wersji filmu. Wiele aktorek ubiegało się o tę rolę: (Kliknij tu po szczegóły) Dorothy Jordan, Frances Fuller, Andrea Leeds, Anne Shirley, Marsha Hunt, Elizabeth Allan, Geraldine Fitzgerald i Priscilla Lane. Faworytką Louis B. Mayera była Maureen O'Sullivan. Inna kandydatka, Janet Gaynor zrezygnowała z dalszej kariery filmowej. W końcu Selznick zdecydował się na Marshę Hunt, nawet powiedział jej, że znalazł swoją Melanię, ale miała zachować to w tajemnicy jeszcze kilka dni, aż on do niej zadzwoni. Ona jednak tego telefonu się nie doczekała ponieważ w międzyczasie pojawiła się Olivia de Havilland.

Pewnego dnia w biurze Cukora pojawiła się Joan Fontaine, sądząc, że Cukor chce by z nim zrobiła czytanie roli Scarlett. Kiedy dowiedziała się, że była brana pod uwagę do roli Melanii odmówiła, ale wspomniała o swojej starszej siostrze, Olivii.

Olivia była zachwycona persektywą zagrania Meli i spotkała się z Cukorem w jego domu, by przeczytać dla niego rolę. George wcielił się w postać Scarlett i Olivia jest pewna, "że to jego występ zdobył jej tę rolę". Cukor i Selznick byli zachwyceni; znaleźli to czego szukali.

Był tylko jeden problem. Olivia miała kontrakt z wytwórnią Warnerów. Jack Warner pozostawał niewzruszony: Davis jako Scarlett, Flynn jako Rhett i WTEDY Selznick może dostać de Havilland.

Olivia była na tyle zdeterminowana, że poszła prosić Jacka Warnera osobiście, jednak daleko nie zaszła, bo on cały czas próbował ją odwieść od tego pomysłu, mówiąc, że ten film będzie "największą klapą w historii".

Olivia wcale się jednak nie zniechęciła i postanowiła wykorzystać fakt, że dobrze znała się z żoną Warnera, Ann. Zaprosiła ją na kawę i przedstawiła sytuację. A Ann później udało się przekonać męża by pozwolił Olivii zrobić ten film. (Choć jak wspomina Olivia, to wcale nie było tak altruistyczne z jego strony; została wypożyczona za Jimmy Stewarta i pewną sumę pieniędzy.)

Podpisała swój kontrakt 13 stycznia i tego samego dnia wysłała telegram do Margaret Mitchell: "FAKT, ŻE ZAGRAM MELANIĘ OZNACZA DLA MNIE SPEŁNIENIE DŁUGO OCZEKIWANEGO MARZENIA. TERAZ MAM TYLKO NADZIEJĘ, ŻE UDA MI SIĘ ZAGRAĆ Tę ROLĘ TAK, BY PANI BYŁA USATYSFAKCJONOWANA". M. Mitchell przesłała Olivii swoje najlepsze życzenia. Napisała także: "Wiem lepiej niż ktokolwiek inny, jak trudna będzie rola Melanii. To jedna z moich ulubionych postaci w książce i nie mogę się doczekać, aż zobaczę ją na ekranie w Pani interpretacji".

"Pan Howard był prawie jednomyślnie typowany przez Południowców do roli Ashleya..." - Margaret Mitchell w liście do Davida Selznicka, 14 stycznia 1939 "Moją misją tutaj są pieniądze i kim ja jestem żeby odrzucić taką propozycję?" - Leslie Howard w liście do swojej córki

Leslie Howard był nawet bardziej niechętnie nastawiony do roli Ashleya niż Clark Gable do roli Rhetta. On nigdy nie przeczytał książki, nie chciał grać kolejnej, niewyraźnej postaci, nie chciał grać w filmie kostiumowym i wiedział, że mając czterdzieści pięć lat był za stary by zagrać dwudziestoletniego młodzieńca.

Ale Leslie Howard wydawał się jedynym możliwym kandydatem. Dziesiątki aktorów były brane pod uwagę, a George Cukor do zdjęć próbnych używał tzw. "scenę w sadzie", rozmowę Ashleya ze Scarlett w Tarze, w czasie wojny. Wśród potencjalnych kandydatów byli m.in.: Ray Milland, Richard Carlson, Shepperd Strudwich, John Howard, Robert Young. Douglass Montgomery zagrał scenę próbną z Vivien Leigh jako Scarlett; na Selznicku żadnego wrażenia nie zrobił występ Jeffrey'a Lynn'a, który zagrał z Paulette Goddard. Test Melvyna Douglasa (z Laną Turner jako Scarlett) Selznick uznał za pierwszą inteligentną interpretację Ashleya, ale stwierdził, że jest "zbyt muskularny" i wyglądem nie przypomina Ashleya.  (obsadzanie roli Ashleya słowami Selznicka)

Tak więc Selznick cały czas powracał do Howarda. Dowiedział się, że Leslie niedawno założył swoją własną firmę i zakupił prawa do kilku dzieł literackich oraz że Howard miał jedną życiową ambicję -  zostać producentem. Więc Selznick zaproponował Howardowi, że w zamian za jego udział w Przeminęło z Wiatrem Selznick uczyni go współproducentem swojego najnowszego filmu, Intermezzo, w którym Leslie miałby także zagrać główną rolę, a partnerowałaby mu Ingrid Bergman. Ponadto za oba filmy miał zagwarantowaną sześciocyfrową sumę. Wobec tego jego kontrakt podpisany został 13 stycznia 1939. 

Tego samego dnia wysłał zabawny telegram do M. Mitchell: "JA WCALE NIE ZAZDROSZCZĘ RHETTOWI PONIEWAŻ DZIĘKI PANI, TO Z MELANIĄ CHCIAŁEM BYĆ. A TAK NA POWAŻNIE, TO DLA MNIE WIELKI ZASZCZYT, ŻE ZOSTAŁEM WYBRANY BY ZAGRAĆ JEDNĄ Z RÓL Z PANI KSIĄŻKI, TYTUŁU KTÓREJ NIE MOGĘ SOBIE NIESTETY TERAZ PRZYPOMNIEĆ."

Margaret Mitchell odpowiedziała, że czeka z niecierpliwością, aż zobaczy go na ekranie i pożyczyła mu wszystkiego najlepszego.

25 sierpień 1938: Clark Gable, Louis B. Mayer, David Selznick i przedstawiciel MGM, A. Lichtman podpisują kontrakt w ramach którego Gable zostanie wypożyczony do Selznick International.

13 styczeń 1939: kontrakty podpisują Vivien Leigh, Leslie Howard i Olivia de Havilland.