In 1956 maakte Feleke onderdeel uit van de Ethiopische ploeg van twaalf mensen die deelnamen aan de Olympische Spelen van Melbourne. Dit was voor het eerst in de olympische geschiedenis dat dit land een ploeg afvaardigde. Feleke finishte op de marathon in 2:53.37 en eindigde hiermee op een 29e plaats. De wedstrijd werd gewonnen door de FransmanAlain Mimoun in 2:25.00.