Kupiony za 950.000 funtów, King miał zastąpić na City Ground odchodzącego do West Ham United Marlona Harewooda. W Nottingham zawodnik spędził dwa sezony. W pierwszym zdobył dla klubu 6 bramek, drugi - po bardzo udanej jesieni (9 bramek) – dokończył na wypożyczeniu w Leeds United. Wprawdzie jego Nottingham Forest spadł do League One, to sam King został w Championship - na początku sezonu 2005/06 wypożyczył go bowiem Watford. Na Vicarage Road szybko stał się ulubieńcem kibiców - 12 bramek w 21 spotkaniach sprawiło, że Watford, gdy tylko minął okres wypożyczenia, wykupił Kinga z Nottingham za 500.000 funtów. Do końca rozgrywek napastnik zdobył jeszcze kolejnych 10 bramek, stając się tym samym pierwszym zawodnikiem Szerszeni od czasów klubowej legendy - Luthera Blissetta, który zdobył dla Watfordu przynajmniej 20 bramek w jednym sezonie. Klub awansował do Premier League, a piłkarz dzięki swojej znakomitej grze zyskał wśród fanów przydomek - King of Vicarage Road.