Stoltenberg var utbildad möbelsnickare men ägnade sig huvudsakligen åt måleri. Hans bilder är måleriska med intensiv kolorit. Stoltenbergs bohemiska särprägel förstärktes såväl genom hans dövhet som genom hans verksamhet som kringresande porträttör på landsbygden.