У дорослому футболі дебютував 2002 року виступами за «Віган Атлетік», в якому провів п'ять сезонів, взявши участь у 145 матчах чемпіонату. Більшість часу, проведеного у складі «Віган Атлетік», був основним гравцем захисту команди.
До складу клубу «Евертон» приєднався в липні 2007 року. У першому сезоні в «Евертоні» Бейнс грав нерегулярно, провівши в цілому 29 ігор за клуб. У сезоні 2008/09 Бейнс став твердим гравцем стартового складу ««Евертона».
У вересні 2010 року підписав новий контракт з «Евертоном» до кінця сезону 2014/15.
У січня 2015 року Бейнс зробив свою 45-ю гольову передачу в АПЛ і став найкращим асистентом в історії ліги серед захисників, обійшовши за цим показником Грема Ле Со.
3 березня 2010 року дебютував в офіційних матчах у складі національної збірної Англії в товариській грі проти збірної Єгипту, яка завершилася перемогою європейців з рахунком 3-1.
Був обраний в попередній список з 30 гравців на участь в ЧС-2010, але у остаточну команду з 23 футболістів не потрапив, програвши місце лівому захиснику Стівену Ворноку.
Наразі провів у формі головної команди країни 6 матчів.
Англія
.svg){kind=small}
