In 2004 Aavo Sarap became the head coach of then in II LiigaJK Tallinna Kalev. The team was promoted to Esiliiga where they missed out on promotion in 2005, but in 2006 Sarap lead Kalev to promotion playoffs where they beat JK Viljandi Tulevik in two match aggregate by an away goal.  In 2007 Sarap lead Tallinna Kalev to 6th place finish as the best amateur team in the top division Meistriliiga. In 2008 the club again impressed by staying in the top division after finishing 8th this time around. In 2009 when Kalev was on the verge of relegation Tallinna Kalev's and Aavo Sarap's successful alliance found its end. 
Sarap is also the former coach of Atlantis FC and descended with the team in the 2009 season.