Die ursprünglichen Bewohner waren Arawak. Die Insel wurde 1499 von den Spaniern entdeckt. Sie sollen am 26. Juli an Land gegangen sein, dem Namenstag der Heiligen Anna, und nannten die Bucht Bahia de Santa Ana („Sint Annabaai“). 1515 wurden fast alle Arawak als Sklaven nach Spanien verschleppt. 1527 ließen sich die Spanier endgültig auf Curaçao nieder.

1634 wurde Willemstad von den Niederländern erobert. Das Gebiet östlich der St. Annabaai wurde De Punt („der Punkt“) genannt; im Inseldialekt Papiamentu punta. Später wurde daraus Punda. Auf „dem Punkt“ wurde 1635 ein Fort gebaut, um den Hafeneingang zu beschützen: Fort Amsterdam. Es ist das älteste Fort der Westindischen Kompanie auf Curaçao. Um das Fort herum wuchs die Stadt. 1707 wurde auf der gegenüberliegenden Baai-Seite ein neues Viertel gegründet: Otrabanda (aus Papiamentu: „die andere Seite“).

Seit 1958 ist Willemstad Sitz des römisch-katholischen Bistums Willemstad, das aus der 1752 errichteten Apostolischen Präfektur Curaçao und dem späteren Apostolischen Vikariat hervorging. Hauptkirche ist die Kathedrale Königin vom heiligen Rosenkranz.

Am 30. Mai 1969 brach in Willemstad ein Arbeiteraufstand aus, bei dem der Gewerkschaftsführer Wilson Godett angeschossen wurde. Daraufhin legten wütende Arbeiter in der Heerenstraat Feuer. Die Niederlande griffen in den Konflikt ein, indem sie 300 Marinesoldaten einflogen, um die Ordnung wiederherzustellen. Godett gründete wenige Tage später mit seinen Mitstreitern die Partei Frente Obrero i Liberashon 30 di Mei (FOL), die bei den folgenden Wahlen rund ein Viertel der Stimmen erobern konnte.

1997 setzte die UNESCO die Innenstadt auf die Liste der Weltkulturgüter. Bis zum 10. Oktober 2010 war Willemstad Hauptstadt der Niederländischen Antillen.