Batista was born on September 9, 1964, in the Cabo Verde islands off the coast of Africa and came to Greece as a European, having acquired first Portuguese and later Dutch citizenship. Batista's uncle, Noni Lima, already had a successful career in Greece at Panionios.
Batista played for Ethnikos Piraeus from 1987 until 1989 when he moved to AEK. At AEK, Batista established himself as one of the better forwards of the Greek league, earning himself the nickname "the Gulitt of Greece".
After the 1992 season, Batista made the jump to Olympiakos at a time when the Piraeus club was rebuilding through acquiring much AEK talent (Refik Sabanadzovic, Alekos Alexandris and coach Dusan Bajevic).