With his father, uncles and grandfather being involved in running a local "lucha libre" promotion and school in Durango Andrade began training for a professional career from an early age, initially by playing around with his father and uncles, but later began to train seriously for a career in the wrestling ring. He made his professional wrestling debut on October 3, 2003, a month before his 14th birthday, but only after his father signed a waiver for the local boxing and wrestling commission to issue him a license. He began working under the ring name Brillante Jr. in honor of his father. Working for his family's wrestling promotion Andrade used the name "Brillante Jr." from 2003 through early 2007. During that period of time, he got involved in a storyline rivalry with his uncle who wrestled as "Zafio", leading to his first ever "Lucha de Apuestas", or bet match. By defeating Zafiro he won his first headline match, forcing Zafiro to have all his hair shaved off after the match per "lucha libre" traditions. He later won another "Lucha de Apuestas" match, forcing the masked wrestler Camorra to unmask in the middle of the ring and reveal his real name. During this time period Andrade also competed as the "enmascarado" (masked) characters "Guerrero Azteca" ("Aztec Warrior") and "Rey Azteca" ("Aztec King") on occasion. In 2007 he signed with Consejo Mundial de Lucha Libre ("World Wrestling Council"; CMLL), and began training under CMLL head trainer El Satánico. He made his CMLL in-ring debut on February 27, working as "Brillante" just like his father had. In June CMLL changed his name, rechristening him La Sombra ("The Shadow"). CMLL previously had other people work under the name "La Sombra" in the 1980s and 1990s; CMLL did not promote the most recent La Sombra as having any relation to the previous incarnations at all, although it was later subtly acknowledged relationship was acknowledged when La Sombra began wrestling in a black and silver version of his father's mask. La Sombra quickly moved up the ranks of CMLL in the months after his debut. The first sign of CMLL putting their faith in La Sombra came when the promoters him teamed up with CMLL's main good guy (known as a "técnico" in Spanish) Místico for their annual "Torneo Gran Alternativa" ("Great Alternative Tournament") where a rookie and a veteran team up.