If you're looking to read about Conan's early life before, and just as, he left Cimmeria, then these are works to look for. These tales cover Conan's story from birth to his late teens. Several stories take place in and around Cimmeria, and about half take place as Conan is struck with wanderlust, having made the decision to trek south to Zamora to learn the skills of being a thief.
Conan OF VENARIUM by Harry Turtledove. Still in print, this book describes Conan's first blood letting on a siege battlefield at age 15. Note that some of the details in this book conflict with previously established "Conan details". But, we can chalk this up to the various interpretations and mouth-to-mouth retellings of tales of the mighty barbarian.
Conan THE BARBARIAN by L. Sprague de Camp and Lin Carter is the novelization of the Arnold movie. Conan's origin story. The novel is quite good and is wearing, over the years, much better than the movie is. This book follows Conan as a child into his early twenties, taking place in Cimmeria and across Hyboria. Many other Conan stories can be considered to take place in between the pages of this book as it covers so much time in Conan's life.
Conan THE BOLD by John Maddox Roberts is one of the best non-Howard Conan works I've read. This book takes place when Conan is quite young, in his late teens. And, in the story, Conan travels the length of Hyboria all the way south to deep, dark Stygia.
Conan THE HUNTER by Sean A. Moore. This is an excellent book, taking place after Conan has left Cimmeria and made his way south to Brythunia. Ancient Shem is visited in this book.
Legions of the Dead by Lin Carter and L. Sprague de Camp is a short story contain in Conan THE SWORDSMAN. Conan is traveling with a band of Aesir raiding into Hyperboria. The cold lands of Asguard are explored in this story, alond with a location in the game: The Fields of the Dead.
The Thing in the Crypt by L. Sprague de Camp and Lin Carter is a famous Conan story telling the tale of Conan finding an ancient broadsword made of Atlantean steel. The two writers incorporated this story into the novel and screenplay for Conan THE BARBARIAN. The story takes place after Conan has left Cimmeria but before he reaches the Hyborian lands. The Kezankian Mountains.
Conan THE DEFIANT by Steve Perry is the first of a four-book-cycle of novels following Conan on his trip south, Cimmeria-to-Hyboria, when Conan is in his late teens. I have liked some of Perry's other works, but, I must admit, these four novels are not something I enjoyed reading. Perry seemed to want to make Conan's universe the D&D universe--but there is too much difference in the two for Perry's idea to meet my approval. This novel begins as Conan reaches the spot where three nations come together: Brythunia, Corintha, and Zamora.
Conan THE INDOMITABLE by Steve Perry is the second in Perry's "travel" quadrilogy. Perry is connecting Conan with the wintery Cimmeria/Asguard/Hyperboria tales to the ones that take place in Hyboria. This middle book follows Conan into a large cave complex beneath the Kezankian Mountains. Again, I feel this book is too much "D&D" and not enough of "Howard's universe as Howard created it", but some may like it (since it definitely does have a different "feel" to it). Note: This book does feel like a novelized version of some of the bigger quests in the game, and for that reason, some may enjoy this book.
Conan THE FREE LANCE by Steve Perry is the third book following Conan's first trek from Cimmeria to Hyboria. Zamora is his destination. Conan thinks he can become a thief to earn his way in the world. Zamora, the nation of thieves, is the ideal place to begin. Although this book is a bit better than the first two in Perry's quadrilogy, it still doesn't live up to some of the other Conan pastiches I've read.
Conan THE FORMIDABLE by Steve Perry concludes Perry's quadrilogy, thank the gods. All four of Perry's books can be considered to take place within the pages of de Camp's and Carter's Conan THE BARBARIAN book mentioned up list. The last two Perry books are better than the first two, but none are high on my Conan recommendation list. I suggest them only for "complete-ists". It is in this book, though, that Conan finally sets his eyes on his destination--the Hyborian kingdom of Zamora.