Stoljarow feierte zunächst auf der Challenger Tour Erfolge. Im Einzel gewann er in seiner Karriere einen Titel sowie vier weitere im Doppel. Auf der ATP Tour feierte er seinen größten Erfolg mit dem Finaleinzug in Chennai, unterlag dort aber dem Tschechen Michal Tabara. Bei Grand-Slam-Turnieren erreichte er im Einzel mit dem Erreichen der dritten Runde sein bestes Ergebnis im Jahr 2000 in Wimbledon.
In den Jahren 2001 und 2002 wurde Stoljarow zweimal in der russischen Davis-Cup-Mannschaft eingesetzt. Er bestritt bei seinen Einsätzen jeweils ein Match im Einzel, beide gegen Schweden: 2001 besiegte er Magnus Norman im Viertelfinale in drei Sätzen, 2002 profitierte er von der verletzungsbedingten Aufgabe seines Gegners Andreas Vinciguerra. Damit war Stoljarow Teil der russischen Mannschaft, die in der Saison 2002 den Davis Cup gewinnen konnte. 2008 spielte er das letzte Mal regelmäßig Turniere.