"Pata pata" is geschreven door Makeba en Jerry Ragovoy en geproduceerd door Ragovoy, Jimmy Wisner, Luchi de Jesus en Severino Dias de Olivera. Het nummer wordt gezongen in het Xhosa; de titel is naar het Nederlands te vertalen als "raak aan, raak aan". Het is ook de naam van een dans die in de jaren '50 populair was in de shebeens van de buitenwijken van Johannesburg.
"Pata pata" was niet het enige nummer dat was geïnspireerd door deze dans. De melodie was gebaseerd op het instrumentale "Phatha phatha" van Shumi Ntutu en Isaac Nkosi, dat weer gebaseerd was op "Noma kumnyama" van Alson Mkhize. In 1956 bracht Dorothy Masuka "Ei yow phata phata" uit dat anders was dan het nummer van Makeba, maar later maakte Masuka haar eigen versie van het nummer dat populair werd vanwege Makeba. Masuka claimde echter dat zij het zelf had geschreven.
"Pata pata" werd oorspronkelijk opgenomen in 1959 door The Skylarks, een groep waar Makeba onderdeel van was. Volgens sommigen werd de eerste opname zelfs al in 1956 gemaakt. In 1967 nam Makeba een nieuwe versie van het nummer op, nadat zij succesvol werd in de Verenigde Staten. In deze versie zit een stuk dat in het Engels gesproken is, waarin Makeba vertelt hoe de dans is ontstaan.
"Pata pata" werd een hit in een aantal landen. In de Amerikaanse Billboard Hot 100 kwam het tot de twaalfde plaats, terwijl het in Venezuela een nummer 1-hit werd. In Nederland piekte de single op de elfde plaats in de Top 40 en de zevende plaats in de Parool Top 20, terwijl in Vlaanderen de vijftiende positie in de voorloper van de Ultratop 50 werd gehaald. Makeba heeft een aantal andere versies van het nummer opgenomen: in 1988 bracht zij het uit als duet met Chayanne, in 1990 bracht zij een eigen versie uit voor haar album Welela en in 2000 werd een nieuwe versie onder de titel "Pata pata 2000" opgenomen voor haar album Homeland. Op 9 november 2008 kreeg Makeba, kort nadat zij "Pata pata" had gezongen in de Italiaanse stad Caserta, een hartaanval waardoor zij overleed; het is het laatste nummer dat zij live heeft gespeeld.
"Pata pata" is vele malen gecoverd. Hitgenoteerde versies zijn afkomstig van Osibisa, dat in 1980 in Nederland en Vlaanderen een hit scoorde met hun versie, Coumba Gawlo, die in 1998 in Wallonië een nummer 1-hit scoorde met haar versie, en Milk & Sugar, die in 2011 een klein hitje scoorden met hun remix onder de titel "Hi-a ma (Pata pata)". Andere versies zijn afkomstig van Jonathan Butler, Howard Carpendale, Manu Dibango, Arielle Dombasle met Mokobé, Tony Esposito, Angélique Kidjo, Helmut Lotti, Tito Puente and His Orchestra, The Skatalites, The Supremes, Thalía, Sylvie Vartan en Otto Waalkes. Daarnaast werd de originele versie in 2009 door Honda gebruikt in een commercial voor hun Accord Crosstour.
