Die Gegend von Recife wurde 1537 von den Portugiesen besiedelt. Doch zwischen 1630 und 1654 befand sich hier der Hauptstützpunkt und das Handelszentrum der Niederländer, die versuchten, den Portugiesen die alleinige Herrschaft über Brasilien streitig zu machen, und im Nordosten ihre Kolonie Neu-Holland errichteten. Vor allem durch den visionären Generalgouverneur Moritz von Nassau erhielt der Ort einen städtebaulichen Schub. Moritz galt als der eigentliche Stadtgründer. Er nannte die Stadt Mauritsstad (Moritzstadt, portugiesisch: Maurícia) und versuchte, die neue Kolonie wirtschaftlich und kulturell weiter zu entwickeln. Die vielen Sümpfe und Inseln wurden von den Niederländern durch das Anlegen von Kanälen bewohnbar gemacht. Aus dieser Zeit sind auch zahlreiche Gebäude erhalten.
1654, nach der Schlacht von Guararapes, mussten die Niederländer die Kolonie jedoch aufgeben. Maurícia wurde portugiesisch. Erst 1710 wurde die Stadt in Vila do Recife umbenannt. 1823 wurde Recife anstelle von Olinda Hauptstadt von Pernambuco.
1930 überquerte LZ127 "Graf Zeppelin" zum ersten Mal nonstop den Südatlantik von Sevilla (Spanien) nach Recife. In Recife befand sich ein Ankermast, an dem die Luftschiffe im Transatlantikverkehr anlegen konnten.
Seit 2001 ist João Paulo (PT) Bürgermeister, er wurde 2004 mit 56,1 % der Stimmen wieder gewählt.