That is, halig fax or holy hair. Its previous name was Horton. The story is that a certain clerk of Horton, being jilted, murdered his quondam sweetheart by cutting off her head, which he hung in a yew-tree. The head was looked on with reverence, and came to be regarded as a holy relic. In time it rotted away, leaving little filaments or veins spreading out between the bark and body of the tree like fine threads. These filaments were regarded as the fax or hair of the murdered maiden. (See Hull.
(in Nova Scotia). So called by the Hon. Edward Cornwallis, the governor, in compliment to his patron, the Earl of Halifax (1749).
Source: Dictionary of Phrase and Fable, E. Cobham Brewer, 1894
More on Halifax from Infoplease: