Born in Nagasaki, Japan, Yoshida had been a defensive midfielder when playing for Grampus's youth team, but was converted to a centre back after promotion to its top team in 2007. In the 2008 season, he was in the starting lineup for most of the league matches with his Serbian teammate Miloš Bajalica. He earned a call-up for Japan's U-23 team in April 2008 and was a member of the Japan team for the 2008 Summer Olympic finals. He scored Nagoya Grampus's historical first goal in the AFC Champions League in the game against Ulsan Hyundai Horang-i on 10 March 2009. He was called up for the national team for the game against Yemen in the 2011 AFC Asian Cup qualification. In December 2009, it was announced that he had transferred to Dutch club VVV-Venlo. He scored a bicycle kick goal for VVV-Venlo off a corner kick on 11 September 2011 against PSV Eindhoven. The match ended in a 3–3 draw. This goal was awarded as " Goal of the Year 2011–2012 " of the Dutch premier Football League. In this season Maya Yoshida scored as a central defender 5 goals in total.
On 30 August 2012, he agreed to join Southampton on a three-year contract for a fee thought to be in the region of £3 million. He made his debut on the 15 September 2012, against Arsenal in a 6–1 defeat, coming on as a 28th minute substitute for Jos Hooiveld. He then made his home debut in a 4–1 win over Aston Villa, playing the whole 90 minutes.
On 9 August 2013, it was announced that Yoshida would be on the front cover of the Japanese Edition of FIFA 14.