Ekipa wysłana na poszukiwanie plenerów przemierzyła całą Azję, nie wyłączając Bali i Borneo. Ostatecznie zadecydowano, że film zrealizowany zostanie w Malezji. Zdjęcia kręcono w całym kraju, m.in. w porcie Penang, na plażach porośniętej bujną roślinnością wyspy Langkawi, a także w słynących z ciekawej architektury wioskach w dżungli otaczającej położone na południu Ipoh.
Jak na epicki film przystało, na planie „Anny i króla” stanęły monumentalne dekoracje. Realizacja licznych scen parad z udziałem setek statystów i egzotycznych zwierząt wiązała się z niewyobrażalnymi problemami. Andy Tennant mówi: „Wiedziałem, że nie będzie łatwo, ale rzeczywistość przerosła moje najśmielsze oczekiwania. Często pracowaliśmy w nieznośnym upale, z insektami, słoniami, końmi, wieloma kamerami i helikopterami. Można to było znosić przez tydzień, ale pół roku? Minęło trochę czasu, zanim się przyzwyczaiłem”.
Nad wszystkim górowała dekoracja przedstawiająca pałac królewski opisany w scenariuszu jako „wielobarwny bastion niezwykłej architektury zajmujący powierzchnię 20 bloków mieszkalnych, miasto w mieście, z którego rozciąga się zapierająca dech w piersiach panorama na strzeliste wieże i mieniące się złotem zabudowania odzwierciedlające niegdysiejszą chwałę Syjamu”.
