Zimą 1998 przeszedł do angielskiego Coventry City F.C. Do zespołu ściągnął go ówczesny menedżer Gordon Strachan, który zapłacił za niego 225 tysięcy funtów. Z zespołem zajął 11. miejsce, a rok później dopiero 15., ale stał się solidnym defensywnym pomocnikiem. Latem 1999 roku Boateng przeszedł do Aston Villi za 4,5 miliona funtów. W tym samym sezonie doszedł z klubem z Birmingham do finału Pucharu Anglii, jednak zespół uległ Chelsea 0:1. W Aston Villi przez 3 sezony rozegrał blisko 130 meczów (we wszystkich rozgrywkach) i ugruntował swoją pozycję, będąc jednym z lepszych zawodników na swojej pozycji w lidze.
W 2002 roku znów zmienił klub. Middlesbrough F.C. zapłacił za niego 5 milionów funtów. W lidze zadebiutował w 1. kolejce, 17 sierpnia 2002 w zremisowanym 0:0 meczu z Southampton. Pod koniec sezonu doznał kontuzji kostki i poddał się operacji, dzięki czemu powrócił w pełni sprawny do składu w sezonie 2003/2004. W tamtym sezonie wywalczył Puchar Ligi Angielskiej, po wygranym 2:1 finale z Leicester City F.C. Było to pierwsze takie trofeum „Boro” w historii. W sezonie 2004/2005 przez 8 tygodni leczył kontuzję palca u nogi, a po powrocie poprowadził Middlesbrough do zajęcia 7. miejsca w lidze, gwarantującego start w Pucharze UEFA.