Mendes tekende zijn eerste profcontract in 1998 bij Vitória SC, maar werd daardoor eerst een jaar uitgeleend aan FC Felgueiras voordat hij zijn debuut op het hoogste niveau in Portugal mocht maken. Daarop speelde hij in vier jaar meer dan tachtig wedstrijden voor de middenmoter. Mendes speelde zich er in de kijker van José Mourinho, die hem voor aanvang van het seizoen 2003/04 naar FC Porto haalde. Hiermee werd hij dat jaar voor het eerst in zijn loopbaan landskampioen én won hij de UEFA Champions League 2003/04, door als basisspeler in de finale AS Monaco met 0-3 te kloppen.
Na één jaar Porto ging Mendes voor het eerst de grens over en tekende hij bij het Tottenham Hotspur van toenmalig trainer Martin Jol. Daarvoor speelde hij in zijn eerste jaar meer dan 25 competitiewedstrijden, maar in zijn tweede seizoen kwam hij voor de winterstop niet verder dan zes optredens. Daarop ging Mendes in januari 2006 weg, naar competitiegenoot Portsmouth. Dat was net gekocht door zakenman Alexandre Gaydamak en haalde behalve Mendes nog een reeks nieuwe spelers. Hij kreeg er in augustus 2006 tijdens een wedstrijd tegen Manchester City een elleboog van Ben Thatcher en kwam in het ziekenhuis bij bewustzijn.[2]. In het seizoen 2007/08 won Mendes met Portsmouth de FA Cup, door als basisspeler de finale met 1-0 te winnen van Cardiff City.
In augustus 2008 tekende Mendes voor drie jaar bij Glasgow Rangers[3]. Daarvoor speelde hij in zijn eerste jaar bijna alle wedstrijden en vierde hij aan het eind van het seizoen 2008/09 voor de tweede keer in zijn loopbaan een landkampioenschap. Toen een half jaar later Sporting Lissabon aanklopte, wilde hij graag terug naar zijn geboorteland. In januari 2012 viel hij uit met een zware blessure. Hij maakte zijn comeback in april 2012 en speelde de laatste wedstrijden van het seizoen mee. Hierna gaf Mendes aan te stoppen met profvoetbal.
Mendes speelde in november 2002 tegen Schotland zijn eerste wedstrijd als Portugees international en drie maanden later zijn tweede[4]. In 2003 werd Luiz Felipe Scolari bondscoach van Portugal en die zag het niet in hem zitten. Hij speelde ruim vijf jaar geen interlands totdat Carlos Queiroz in 2008 Scolari opvolgde en Mendes weer selecteerde. Deze bondscoach was wel dusdanig gecharmeerd van Mendes dat hij hem meenam naar het WK 2010. Daar liet Queiroz hem de poulewedstrijden tegen Ivoorkust (0-0) en Noord-Korea (7-0 winst) van begin tot eind spelen en hem in de derde wedstrijd tegen Brazilië (0-0) in de 64 minuut invallen voor Pepe.