The first municipality with the name Heby was created in 1952, during the first of the two nation-wide municipal reforms in Sweden, through the amalgamation of three original units in Västmanland County. The name was taken from the settlement Heby, which had been a municipalsamhälle (a kind of borough) since 1887. In 1971 three more former entities were added.
Heby used to be part of Västmanland County, which borders Uppsala County to the west. In September 2005 it was reported that the municipality was permitted to be part of Uppsala County after intense lobbying in the late 1990s, following a municipal poll in 1998 where the majority was in support of the county transition. The transition took place on January 1, 2007. There were, however, forces who worked for the transition not to take place.