Stoltenberg began playing tennis at the age of 10 on an antbed court where his father owned a cotton farm in the far west of New South Wales.

He was the world junior boys’ champion in 1987 and turned professional in the same year.

In Davis Cup he held a 9-5 record from eight ties. He represented Australia at the Atlanta 1996 Olympics, losing in the second round of the singles.

He is married to former pro Andrea Strnadova and they have two children. He won singles titles at Coral Springs 1996 and 1997, Birmingham 1994 and Manchester 1993.

He won doubles titles at Sydney Outdoor 1993 (w/Stolle), San Francisco 1991 (w/Masur), Manchester, Singapore (w/Kratzmann) and Brisbane 1990 (w/Woodbridge).

His highest singles ranking was No.19 in October 1994 and in doubles he made it to No.23 in March 1991.

Taking on the role of coach, he teamed with Lleyton Hewitt at the end of the 2001 season for 18 months, helping guide Hewitt to his 2002 Wimbledon title before resigning to return to Melbourne.

In 2010 Stoltenberg took a role as a consultant for Tennis Australia that sees him coaching a number of Australian players, including rising female star Ash Barty.