Historians believe Subutai was born in the year 1175, probably just west of the upper Onon River in what is now Mongolia. He belonged to the Uriankhai clan, known as the reindeer people, a group of Siberian forest-dwellers who did not live like the plains Mongols to their south. As a result of his upbringing, Subutai lacked the natural horsemanship training from birth that all Mongols possessed, making him an outsider among them. Subutai's family had been associated with the family of Temujin (future Genghis Khan) for many generations. Subutai's great-great grandfather, Nerbi, was supposedly an ally of the Mongol Khan Tumbina Sechen. Subutai's father, Jarchigudai, supposedly supplied food to Temujin and his followers when they were in dire straits at lake Baljuna, and Subutai's elder brother Jelme also served as a general in the Mongol army and was a close companion of Temujin. Jelme rescued a severely wounded Temujin (hit by an arrow from Jebe, then an enemy) in the process of unification of the Mongolian plateau. Another brother, Chaurkhan (also romanized as Ca'urqan) is mentioned in the Secret History of the Mongols.
Subutai's biography in the History of Yuan opens up with a peculiar anecdote about the general's early life. Subutai's father was once driving a herd of sheep in order to present them to his overlord, Taizu (Genghis Khan). Encountering robbers, he was seized. Huluhun (Subutai's brother) and Subutai arrived in good time, and with their lances stabbed some of the robbers. Horses and men fell together, and the remainder of the band withdrew and departed. Consequently, they relieved their father’s difficulty, and the sheep were able to attain the emperor’s station.
Despite this close family association, Subutai may be considered proof that the Mongol Empire was a meritocracy. He was a commoner by birth, the son of Jarchigudai, who was supposedly a blacksmith. When he was 14 years old, Subutai left his clan to join Temujin's army, following in the footsteps of his older brother Jelme who had joined when he was 17 years old, and he rose to the very highest command available to one who was not a blood relative to Genghis. Within a decade he rose to become a general, in command of one of 4 tumens operating in the vanguard. During the invasion of Northern China in 1211, Subutai was partnered with the senior Mongol general Jebe, an apprentice and partnership they would maintain until Jebe's death in 1223. In 1212 he took Huan by storm, the first major independent exploit mentioned in the sources. Genghis Khan is reported to have called him one of his "dogs of war," who were 4 of his 8 top lieutenants, in The Secret History of the Mongols:
"They are the Four Dogs of Temujin. They have foreheads of brass, their jaws are like scissors, their tongues like piercing awls, their heads are iron, their whipping tails swords . . . In the day of battle, they devour enemy flesh. Behold, they are now unleashed, and they slobber at the mouth with glee. These four dogs are Jebe, and Kublai (different than Kublai Khan), Jelme, and Subotai."
Subutai seems to have been identified from early on by Temujin as special, and given rare opportunities for growth. Appointed to the prestigious post of Genghis Khan's ger door guard during his teen years, Mongol histories say that Subutai said to Genghis Khan, "I will ward off your enemies as felt cloth protects one from the wind." This access enabled him to listen on, and later join, the Mongol strategy meetings somewhere around his late teens and early twenties. Throughout most of Genghis Khan's lifetime, Subutai would have the opportunity to apprentice on detached missions under the elite Jebe (1211–12, 1213–14, 1219–23) and Muqali (1213–14), in addition to Genghis Khan himself (1219). It is likely that his unique access to the most brilliant Mongol leaders assisted his growth.