In dispute with.
'At loggerheads' is of UK origin. The singular 'loggerhead' occurs as a name in several contexts - as a species of turtle, a bird and as a place name. Originally, a loggerhead was none of these but was used with the meaning of 'a stupid person - a blockhead'. Shakespeare used it that way in Love's Labours Lost, 1588:
"Ah you whoreson logger-head, you were borne to doe me shame."
A 'logger-head' was literally a 'block-head'. A logger was a thick block of timber which was fastened to a horse's leg to prevent it from running away. In the 17th century, a loggerhead was also recorded as 'an iron instrument with a long handle used for melting pitch and for heating liquids'. It is likely that the use of these tools as weapons was what was being referred to when rivals were first said to be 'at loggerheads'.
The first known use of the phrase in print is in Francis Kirkman's, The English Rogue, 1680:
"They frequently quarrell'd about their Sicilian wenches, and indeed... they seem... to be worth the going to Logger-heads for."
The next year saw the printing of The Arraignment, Trial, and Condemnation of Stephen Colledge. In that text the author makes a clear link between loggerheads and fighting:
"So we went to loggerheads together, I think that was the word, or Fisty-cuffs."
Incidentally, 'fisticuffs' is another two-word term from around the same date that was later amalgamated into a single word. A cuff was a blow with the open hand. A fisty cuff was a cuff using the fist, that is, a punch.
Following the departure of the clown William Kemp from The Lord Chamberlain's Men, the troupe of actors that William Shakespeare worked with for most of his writing and acting career, his place was taken by Robert Armin. In 1605, the diminutive clown Armin, a.k.a. 'Snuff, the Clown of the Globe', had a stab at writing and came up with Foole upon Foole. In this piece he makes the first recorded reference to 'fisty cuffs':
"The foole... falls at fisty cuffes with him."
'Loggerheads' is also the name of three small towns in the UK - in Staffordshire, in Lancashire and in Mold, North Wales. As is 'de rigueur' when a town might have reason to claim to be associated with some phrase or another, each town's residents claim that 'at loggerheads' originated in their home-town. Alas, despite the early citations referring to 'going to' loggerheads, this isn't the case. The towns were named after the term, not the other way about. Nevertheless, the use of 'loggerheads' as a place name has been a boon to stand-up comedians of the 'take my wife...' fraternity. They have been trotting out this classic for years:
'I'm going on holiday - a fortnight at Loggerheads with the wife'.
See other phrases and sayings from Shakespeare.