Iniziò la sua carriera come mezzofondista veloce: nel 1956 partecipò alle Olimpiadi di Melbourne gareggiando negli 800 m, nei 1500 m e, addirittura, nella staffetta 4×400. Passato alle lunghe distanze, nel 1964 a Tokyo sfiorò il podio olimpico giungendo quarto nella finale dei 10 000 m. Centrò il podio quattro anni dopo, vincendo dapprima la medaglia d'argento sui 10000 m e quindi l'oro nella maratona succedendo al connazionale Abebe Bikila, vincitore nelle due precedenti edizioni. Nel 1972, a quarant'anni compiuti, riuscì a conquistare un'altra medaglia olimpica giungendo terzo nella maratona di Monaco di Baviera: solo Bikila, prima di lui, era riuscito a conquistare due medaglie olimpiche nella maratona. Concluse la carriera vincendo la maratona ai Giochi panafricani del 1973.
Nel 1993 Wolde fu arrestato con l'accusa di aver preso parte a un omicidio commesso nell'ambito del Terrore rosso, durante il regime del deposto dittatore Menghistu Hailè Mariàm. Uscito di prigione nel 2002, morì pochi mesi dopo. È stato sposato due volte e ha avuto tre figli.