As suspected, the dog was already domestic before the Neolithic and that was certainly the case in Europe. This seems confirmed by new findings of dog remains in the shell middens of the Muge area, the main clutural group of pre-Neolithic Portugal.
Cleia Detry and Joao Luis Cardoso, On some remains of dog (Canis familiaris) from the Mesolithic shell-middens of Muge, Portugal. Journal of Archaeological Science, 2010. Pay per view.
Just for the record. Notice that the oldest known dog skeleton is from Aurignacian Belgium although its mtDNA line is now extinct.