As he worked his way through the Brewers' farm system, Villanueva was called up to the Brewers from Double-A Huntsville on May 22, 2006. He made his Major League debut against the Cincinnati Reds on May 23, 2006, pitching a scoreless inning. After being optioned back to the minors, Villanueva was recalled again, making his first career Major League start for the Brewers against the Cincinnati Reds.
After a successful 2006 campaign, Villanueva entered the 2007 spring training in competition for the Brewers fifth spot in the starting rotation. Despite pitching well, he lost the job to Claudio Vargas. Instead, manager Ned Yost elected to put Villanueva into the bullpen as a middle relief pitcher. Villanueva pitched well in his new role and was occasionally used as a long relief pitcher when Elmer Dessens was placed on the DL. On July 2, Villanueva was 6-0 with a 2.64 ERA. Despite his record, Villanueva was accustomed to only being used as a starting pitcher, and had never appeared in more than 25 games in his professional career. Through July and August, he posted a 1-3 record with an ERA of over 9, perhaps a sign of being overworked. Despite his struggles, he was still being used as a middle relief pitcher. On August 20, after pitching 3 perfect innings against the Arizona Diamondbacks and picking up his first career save, he was optioned to the Triple-A Nashville Sounds to make two starts to "polish up" for a September call up when the rosters expand.