The first customers were definitely the hardest. I didn't do any classic marketing, just cold calls and emails. It took a few months to get the first paying user. I did target a specific niche.
I then went in a road trip around the northeast (literally camping in a tent at the nearest KOA or park) hitting different areas where customers were. I'd stop in town, call them up, and tell them I was passing through (which was kind of true) and ask if they could meet for a half hour. I got some of my first meetings that way.
It was extremely inefficient but helped grow the initial user base. It's definitely not an approach I'd recommend to someone - it's kind of ridiculous but it worked.
That said, the customers I was targeting were all part of the same trade association and the word spread that I was actually doing something pretty useful. That led to new customers and a lot of word of mouth.
I only seriously started with traditional outbound marketing this year, which is my 8th year in business. Other than that it's been direct outreach, word of mouth, and attending conferences and drinking my ass off with potential customers (not ideal, but every association has its own vibe and sometimes you gotta do what you gotta do).
Building partnerships with like minded entrepreneurs in your industry is a good approach too (referrals, integrations, etc)
All this said, it took 4 years to make enough money to pay myself and 5 years to hire my first employee which was a customer support manager. "Delegating and elevating" is magic and led to more time to focus on growth. I did a lot of freelancing in those first 4 years to make ends meet. It could definitely be done faster, but I was way more of a n00b than I realized at the time (isn't that always the case?)