Starting out at non-League club Elmstead, Foster made his league debut for Leyton Orient in January 1982 whilst still an apprentice. He moved to Nottingham Forest, for a fee of £50,000 in May 1987, making 72 league appearances under manager, Brian Clough. In September 1989, he became manager Lou Macari's second and most expensive signing for West Ham United for £750,000. Never a regular player under Macari, he became so under new manager Billy Bonds in a team which won promotion from the second division in season 1990-91. Three seasons broken by regular injury followed and after a projected £400,000 move back to Nottingham Forest fell through, when Foster could not agree terms, he remained at West Ham on a weekly contract. A loan to Notts County followed before he eventually moved, for a fee of £100,000, to Watford in March 1994.