What does your tool/service do? Write a blog on "how to do XYZ". Use your personal blog, website, or guest post on Medium, etc.

Be helpful. Share an easy and free way to do it without using your tool/service. Then introduce your tool/service. Share its advantages and some proof that it works. Be genuine and honest, don't oversell it. Acknowledge alternative tools/solutions. Distribute it on reddit, twitter, etc.

If your blog is extremely good, Google Search will pick it up in a couple of weeks.