37 metų 208 cm ūgio australas Vilniuje žaidė 2009–2010 metais. Tuomet klubą treniravo Rimas Kurtinaitis, kuris aukštaūgiui skyrė vaizdingą palyginimą, sakydamas, kad „jei rusai priverčia mešką važiuoti dviračiu, tai mes iš Bayneso padarysime neblogą žaidėją.“
Po etapo Vilniuje jis Europoje žaidė dar tris sezonus, o paskui pasuko į NBA.
A.Baynesas NBA lygoje rungtyniavo devynerius metus. Jis yra atstovavęs „Spurs“, „Pistons“, „Celtics“, „Suns“ ir „Raptors“ klubams.
Iš viso NBA jis sužaidė 576 mačus, aikštėje praleisdavo po 16 minučių, įmesdavo po 6 taškus ir atkovodavo 4,6 kamuolio.
Skambiausi A. Bayneso laimėjimai – 2020 metais Tokijo olimpiadoje iškovotas bronzos medalis su Australijos rinktine ir 2014 metais laimėtas čempiono žiedas su „Spurs“.
Taip pat A.Baynesas tapo Slovėnijos ir Lietuvos čempionu. Aukštaūgio karjera buvo sutrikdyta ir traumos, kai Tokijuje rungtynių metu susižeidė nugarą ir atsidūrė ligoninėje.
Paskutine jo karjeros stotele tapo Brisbano „Bullets“ komanda, kurioje praleido du sezonus. Australijos lygoje praėjusį sezoną aukšaūgis per 14 minučių pelnydavo 7,3 taško, atkovodavo 4,3 kamuolio ir surinkdavo po 8 naudingumo balus.
