Technically speaking, Character Transfers were available mid-2006 and patch 1.12, the one Classic is based on, was released in August of that year so they were there. Newish, but there.
The question of character transfers had been covered in the previous AMA here: Q&A Compilation -- WoW Classic Development Team AMA
I had a mind blank the other day when I spoke on it myself, completely forgetting the timeline for events. 