Your company was new. But the situation you describe is not typical of a startup as commonly understood.
In other words, our success was because we identified a critical missing piece in a profitable industry and built exactly what people were asking for, and more importantly, willing to pay for.
After that success (and a couple more after it), I refuse to ever build something without finding customers first. You have to build products people want, not try to convince people into believing they want your product.