Pochází z Dobrušky. Je absolventem Ostravské univerzity – obor operní zpěv, kde jako lyrický baryton studoval u prof. Michaela Kozelského. Ve studiu dále pokračoval u prof. Vlasty Hudecové a prof. Ivana Kusnjera.
V roce 2008 nastoupil jako sólista operety Národního divadla moravskoslezského Ostrava, kde ztvárnil mimo jiné Kornelia v Hello, Dolly!, Dr. Falkeho v Netopýrovi, Vévodu z Buckinghamu ve Třech mušketýrech nebo Fernanda de Champlatreux v Mamzelle Nitouche. Od roku 2012 je sólistou opery Moravského divadla Olomouc, kde debutoval jako Ford ve Verdiho opeře Falstaff. V olomoucké opeře vystoupil mimo jiné i jako Figaro v Lazebníku sevillském, Papageno v Kouzelné flétně, Tomeš v Hubičce, Ping v Turandot nebo jako dr. Malatesta v opeře Don Pasquale. Martin Štolba se také věnuje koncertní činnosti doma i v zahraničí. Představil se např. na přehlídce hudby českých skladatelů v Londýně nebo na koncertním turné při příležitosti Jeju Summer festival v Jižní Koreji. Jako host vystupuje v Národním divadle moravskoslezském Ostrava, Slezském divadle Opava, Jihočeském divadle České Budějovice, Státním divadle Košice a Národním divadle Brno. V DJKT v Plzni pohostinsky vystoupil v inscenacích operety Pařížský život a opery Jakub Jan Ryba.
Za mimořádné ztvárnění role Papagena v opeře W. A. Mozarta Kouzelná flétna byl vybrán odbornou porotou Herecké asociace do širší nominace na Ceny Thálie 2016 v kategorii Opera.
Veselá vdova byla prvním vskutku světovým Lehárovým úspěchem. Bez nadsázky lze říci, že každé hudební číslo v této operetě je malý hudební skvost. Za všechny jmenujme píseň Hany Glawari o víle Vilje nebo píseň Danila o jeho hýření v nočním podniku U Maxima. více
