The high density of the close-in extrasolar planet HD149026b suggests the presence of a huge core in the planet, which challenges planet formation theory. We first derive constraints on the amount of heavy elements and hydrogen/helium present in the planet: We find that preferred values of the core mass are between 50 and 80 M_E. We then investigate the possibility of subcritical core accretion as envisioned for Uranus and Neptune and find that the subcritical accretion scenario is unlikely in the case of HD149026b for at least two reasons: (i) Subcritical planets are such that the ratio of their core mass to their total mass is above ~0.7, in contradiction with constraints for all but the most extreme interior models of HD149026b; (ii) High accretion rates and large isolation mass required for the formation of a subcritical core of 30 M_E are possible only at specific orbital distances in a disk with a surface density of dust equal to at least 10 times that of the minimum mass solar nebula. This value climbs to 30 when considering a 50 M_E core. These facts point toward two main routes for the formation of this planet: (i) Gas accretion that is limited by a slow viscous inflow of gas in an evaporating disk; (ii) A significant modification of the composition of the planet after as accretion has stopped. These two routes are not mutually exclusive. Illustrating the second route, we show that for a wide range of impact parameters, giant impacts lead to a loss of the gas component of the planet and thus may lead to planets that are highly enriched in heavy elements. In the giant impact scenario, we expect an outer giant planet to be present. Observational studies by imaging, astrometry and long term interferometry of this system are needed to better narrow down the ensemble of possibilities.