She started her international beach volleyball career already in 2001 after finishing her indoor contract in Italy. She teamed up with Dutch star Rebekka Kadijk whose sister Debora decided to quit beach volleyball after the 2000 Summer Olympics. In 2001, 2002 and 2004 Kadijk and Leenstra won three Dutch national titles. In Basel 2002 they reached the final of the European Championships. They lost this final, but still won a silver medal. Their main achievement was made in 2003 when they won the World Cup meeting in Lianyungang (China). They qualified for the 2004 Summer Olympics which was not as successful as they hoped before the start. After the Olympics they decided to split up. Leenstra's next partner was Sanne Keizer with whom she did not reach any notable results with, except a 4th place at a tournament in Montreal.