Build an efficient and reliable product ;-) Besides the development, deliver first class support and bug fixes, understand what your clients need.
To gain a strong brand you need some strategy too. If you don't have a network that allows you to add known companies to your client list, a common strategy is to ask less- or well known companies if they want it for free. In exchange you can use them as a reference.
It's not so much about the development phase, more the marketing. A strong brand indicates the crowd acknowledge you. The product itself should be good and nice looking. You can read several books about entrepreneurs where they tell you how they started.