Оттянутый форвард Гордон является воспитанником Ливерпуля, подписав контракт в июле 1961, через месяц после того, как ему исполнилось 17 лет. Почти полтора года ему пришлось ждать дебюта. Тогда Шенкли дал ему еще 6 шансов показать себя в основе. В следующем году, когда Ливерпуль завоевал первое за много лет чемпионство, Уоллес лишь раз появился в основе - когда заменил травмированного Роджера Ханта.

Сезон 1964-65 стал лучшим для Гордона в Ливерпуле: в 12 матчах он забил 5 голов: дважды на "Энфилде" против Арсенала в матче-открытии. Кстати, этот матч стал первой игрой, освещаемой на ВВС в рамках передачи Match of the day. После этого он потерял шансы на попадание в основу, и перешел в Крю, где за 5 лет принял участие в 94 матчах и забил 20 голов.