Thanks for the suggestion. Found out the issue I think.
I have my cert and key, and CA cert in a different directory then the config file (under stunnel\config). Though I point to them from the config file using full path, it doesn't work when started as service. It's working fine if I start manually from command line.
So, moving my cert/key and CA cert to the config directory, and then remove all the paths in the config file, specifying only the file name of the certs and key made it work.