A rock art panel from Saudi Arabia may well be the oldest record of domesticated dogs. Maria Guagnin has been working on engravings in the Shuwaymis Hills of northwestern Saudi Arabia. She has cataloged over 1400 images from the region including what may be dogs on a leash. This article in Science lays out her work.
Rock art is notoriously hard to date, but if her dates are accurate these engravings are likely 8,000 - 9,000 years old. That edges out Iranian depictions of mans best friend by 1,000 years.