Radciffe and O'Sullivan had set a blinding pace in the early stages, clocking the opening 1000m in three minutes one second.
Last year's World Championship silver medallist led for the first 20 laps of the race, attempting to tire her opponents into submission before the kick for home.
But Tulu and Gete Wami, who pipped Radcliffe to gold in the World Championships, moved into the lead with five laps remaining, as the British record holder began to wilt.
On the final lap Tulu stormed clear of the pack to win in 30 minutes 17 seconds, with Wami finishing five seconds behind in second and Fernanda Ribeiro third.
Brave
But the British star, who made a second brave attempt to renew her quest for gold in the final few laps, came home just one place out of the medals in a time of 30 minutes 27 seconds.
Radciffe and O'Sullivan had set a blinding pace in the early stages, clocking the opening 1000m in three minutes one second.
O'Sullivan, who had already bagged a silver medal in the 5000m, dropped off the pace allowing the leading pack of five to slug it out for the medals.
But Radcliffe, who was in tears at the finish after just missing out on the medals, failed to find an extra gear, allowing Tulu, Wami and Ribeiro to clinch gold, silver and bronze.
After the tears had cleared, Radcliffe said: "The field was a lot stronger than last year when I got the silver.
"I knew they had a strong kick so I had to run as fast as I could to try and tire them but nobody helped me out.
"I was just waiting for two of them to drop off - one of them did eventually and I was surprised how well Ribeiro ran - but she always does seem to save it for the big occasion," added a disappointed Radcliffe.
Women's 10,000m final:
1. Derartu Tulu (Ethiopia) 30:17.49
2. Gete Wami (Ethiopia) 30:22.48
3. Fernanda Ribeiro (Portugal) 30:22.88
4. Paula Radcliffe (Britain) 30:26.97
5. Tegla Loroupe (Kenya) 30:37.26
6. Sonia O'Sullivan (Ireland) 30:53.37
7. Li Ji (China) 31:06.94
8. Elana Meyer (South Africa) 31:14.70
9. Lidiya Grigoryeva (Russia) 31:21.27
10. Yuko Kawakami (Japan) 31:27.44
11. Olivera Jevtic (Yugoslavia) 31:29.65
12. Berhane Adere (Ethiopia) 31:40.52
13. Lyudmila Biktasheva (Russia) 31:47.10
14. Alice Timbilil (Kenya) 31:50.22
15. Chiemi Takahashi (Japan) 31:52.59
16. Libbie Hickman (U.S.) 31:56.94
17. Sally Barsosio (Kenya) 31:57.41
18. Asmae Leghzaoui (Morocco) 31:59.21
19. Jelena Celnova-Prokopcuka (Latvia) 32:17.72
20. Harumi Hiroyama (Japan) 32:24.17