Der Ursprung des Palais, welches einer der letzten Überbleibsel der ehemaligen barocken Gartenvorstadt auf der Wieden ist,  liegt vermutlich im Jahr 1697. Eine alte Ansichtsskizze zeigt das Palais als eher schmuckloses Gebäude mit flachem Mittelrisalit  und vorstehenden Seitentrakten, was dem Gebäude seine U-Form gab. Als einer der Eigentümer ist der kaiserliche Kammermaler Martin Meytens bekannt. Nachdem um 1815 Leopold Graf Kinsky die Seitentrakte des Hauses durch Adam Hildwein aufstocken lassen hatte, entstand ein prächtiges klassizistisches Palais. Im Verlaufe des Jahrhunderts wurden noch weitere bauliche Veränderungen vorgenommen, was dem Gebäude schliesslich ein völlig neues Erscheinungsbild verlieh. Zudem entstand aus dem bisherigen Ehrenhof ein geschlossener Innenhof, worauf man das Palais von der Strasse aus nicht mehr sehen konnte. Später wurden die Fassaden auf allen Seiten neu gestaltet. Seit 1948 beherbergt das Palais einen Kindergarten und Mieträume und ist Im Besitz der Pfarre Wieden. Das Gartenpalais Colloredo ist geteilt in einen barocken Gartentrakt und einen historistischen Gassentrakt.