I see that it is really popular with web services nowadays to have their phone number in the header of the website. Is it really that effective? Does it make the company look more legit?
In general, adding information like phone numbers or physical addresses to a site, makes it appear more trustworthy (or 'legit'). In a number of tests that I know of, this has been the case.
However, the side effect of putting your number in your header is that people will call you more, so don't do it unless you can actually handle the support calls. Zappos place their phone number very prominently in their header because they want to be called, so it fits in with their overall strategy.
Don't just put a phone number in your header to look 'legit'. Do it because you are 'legit' and because you want people to call you.
If it's a common user task to visit the site to get the phone number and then call, then your users will appreciate it. If the business wants then to do this, even better!
It's a UX pattern I always apply when designing a site for a business where the service performed is not necessarily done online.
If the number is needed to help a user out of a jam or as a means of getting support, consider fixing the site issues that lead to the calls.