A Arg ("cidadela", em persa) foi construída durante o reinado de Tamaspe I (r. 1524–1576) do Império Safávida (1502–1736), e foi renovada, mais tarde, pelo imperador zande Carim Cã (r. 1750–1779). Maomé Cã Cajar (r. 1742–1797) escolheu Teerão para sua capital. A Arg tornou-se na sede da corte do Império Cajar (1794–1925) e o Palácio do Gulistão na residência oficial da família real daquela dinastia.

Em 1865, o palácio foi reconstruído por Haji Abol-hasan Mimar Navai, alcançando a sua forma actual. Durante a era Pálavi (1925–1979), o Palácio do Gulistão foi usado para recepções formais, tendo os soberanos Pálavi construído o seu próprio palácio no Complexo Palaciano de Niavaran. As cerimónias mais importantes realizadas no palácio durante a era Pálavi foram a coroação de Reza Pálavi (r. 1925–1941) no Takht-e Marmar ("Trono de Mármore") e a coroação de Maomé Reza Pálavi (r. 1941–1979) na Galeria do Museu.

Entre 1925 e 1945, uma grande parte dos edifícios do palácio foram destruídos por ordem de Reza Pálavi, o qual acreditava que o centenário palácio dos Cajar não devia impedir o crescimento duma cidade moderna. No lugar dos velhos edifícios foram erguidas modernas estruturas em estilo comercial, durante as décadas de 1950 e 1960. Atualmente, o Palácio do Gulistão é administrado pela Organização do Património Cultural do Irão. No dia 11 de Outubro de 2005, aquele organismo apresentou o palácio com vista à inclusão na Lista do Património Mundial em 2007 da UNESCO.