Soldering stainless is a learned skill. You have to experiment with different combinations of solder and flux to learn what's right for you. Also, you have to get the heat just right. This is nowhere near as forgiving as sweating copper pipe. I have 3 or 4 different silver-bearing solders with matched fluxes. You haven't mentioned what you mean by "Stainless"; is it 300 or 400 series, or unknown? I don't like to solder 300 series, and that's why I only use 416 for stainless furniture. Stainless simply isn't as easy to solder as plainer steels.
Staybrite solder and Stayclean flux is a popular combination. I also have good luck with the paste-type silver solders for stainless, as sold by Rio Grande. A good old standby is TIX, but it is not as pretty or corrosion resistant.
Some people have mentioned using a heat gun to melt the solder, laying little strips along the solder lines, fluxing, and heat-gunning. I have yet to try this, but it sounds interesting.