Stajan attended St. Timothy's Elementary School and Iona Catholic Secondary School. As a young hockey player, Stajan played for such minor organizations as The Toronto Red Wings and Mississauga Senators. He is of a Slovenian decent, from Dolenjska.
Stajan was drafted 79th overall by the Belleville Bulls in the 2000 Ontario Hockey League priority selection. After scoring 33 goals and 52 assists with the Bulls, he was selected by the Toronto Maple Leafs in the second round of the 2002 NHL Entry Draft with the 57th overall selection. Stajan played one game in Toronto at the end of the junior campaign, in which he scored his first NHL goal on his first shot against the Ottawa Senators' goaltender Martin Prusek.
At the age of 20, Stajan was able to make the Maple Leafs' roster. In his first full NHL regular-season, he was selected to the NHL All-Star Young Stars team as a forward after Atlanta Thrashers'Garnet Exelby had to step out of the game due to an injury. Stajan had a goal and an assist in the game.
While the 2004-05 NHL season was canceled due to the lock-out, Stajan played for the St. John's Maple Leafs, the American Hockey League affiliate of the Toronto Maple Leafs. During the 2005-2006 season, Stajan tied Marian Hossa for first place in the NHL with eight shorthanded points (four goals, four assists). On September 13, 2006, the Leafs signed Stajan to a two-year contract worth $1.75 million. On July 7, 2008, Stajan re-signed again with the Maple Leafs, Signing a two-year, $3.5 million contract.
Stajan wears the uniform number of 14, which he selected in honour of his uncle Robert, who wore the number 14 for basketball before passing away from cancer at age 22. Maple Leafs legend Dave Keon, who played for the Maple Leafs during their last Stanley Cup victory in 1967, also wore 14. He distanced himself from the franchise during the Harold Ballard ownership era, and held a grudge because his number was never retired. Stajan has stated that if the Leafs wanted to retire the number, he would immediately surrender it.