Ochoa was signed as a free agent by the Cleveland Indians on May 3, 2000. He struggled offensively during his six years in the Indians organization, but did receive a promotion to Triple-A Buffalo in 2006. After the 2006 season, Ochoa signed with the San Francisco Giants and was invited to spring training. Ochoa spent all of 2007 with Triple-A Fresno, batting .296 in 47 games. Ochoa started 2008 in Triple-A again, but was called up to the major league team after batting .318 and stealing 20 bases in 84 games. He made his major league debut on July 12, 2008.