Maya led the Cuban National Series with a 1.61 earned run average (ERA) in 2004–05, and followed that up with a 7–9 record and a 3.79 ERA in 2005–06.
In the 2008–2009 Cuban National Series Season Maya finished with a 13–4 record and seven complete games, and finished second amongst League Leaders in ERA with 2.22 ERA. He was also second in Strikeouts with 119, behind Aroldis Chapman who had 130 (after the season, Chapman defected and signed with the Cincinnati Reds). On this performance, Maya won Cuba's equivalent of the Cy Young Award. During six Cuban National Series seasons, Maya accumulated a record of 48–29 and an ERA of 2.51.
In Summer 2009, Maya was expelled from the Cuban national team; the official newspaper Granma referred to "grave problems of indiscipline", presumably following a failed attempt to leave the country without permission. In September 2009, Maya successfully fled Cuba. After living in the Dominican Republic for about nine months, the United States Department of Treasury authorized Maya to sign with a Major League Baseball team.
On July 31, 2010, Maya signed with the Washington Nationals. Maya zoomed through the Nationals minor league system, making only five starts, before getting the call to the majors when rosters expanded in September. In the minors he started two games for the GCL Nationals; one game for the Potomac Nationals; and two games for the Syracuse Chiefs, combining for 21-1/3 innings pitched and an overall ERA of 3.38 ERA. He pitched five inning in his first major league start was on September 7, 2010, against the New York Mets (which also saw the big league debut of Met Dillon Gee. After a rough start (allowing a three-run homer in the first inning to Ike Davis), he retired 11 of the last 12 batters he faced.
On May 29, 2011, Maya was recalled by the Washington Nationals to take the rotation spot of Tom Gorzelanny, who was placed on the disabled list. Collin Balester was optioned to Triple-A Syracuse to make room.