After placing your company Headquarters using the company information window's Build HQ button, you are able to relocate it if you wish.

The Build HQ button will be replaced by View HQ and Relocate HQ buttons as shown in the screenshot. You can then click Relocate HQ at any time and select a new location on the map.

Providing you have enough money to pay for the new building and demolition of the old one, your HQ will be moved. Naturally the fancier building you have, the more expensive it becomes to relocate. The relocation cost is also affected by inflation.

Moving your HQ is instant.