2011-12 Po powrocie z Pucharu Świata U-17 Redmond zagrał w przedsezonowym meczu z Cork City. Wobec braku kilku pomocników Redmond zagrał całą rundę w kwalifikacjach do Ligi Europy przeciwko portugalskiemu Nacional. Po raz pierwszy w karierze rozegrał 90 minut. Zadebiutował w rozgrywkach Championship trzy dni później, ponownie spędzając na boisku cały wymiar czasowy. 31 grudnia 2011 roku zdobył swoją pierwszą bramkę ligową, przeciwko Blackpool. Strzelił także bramkę w starciu z Sheffield United w ramach czwartej rundy Pucharu Anglii. Sezon zakończył z dorobkiem siedmiu goli i zdobył nagrodę Młodego Piłkarza Roku.
2012-13 Pomimo problemów finansowych prezes klubu powiedział, że Jack Butland i Nathan Redmond nie są na sprzedaż. Redmond miał na celu na stałe zostać zawodnikiem pierwszej drużyny. W październiku zagrał po raz pięćdziesiąty w barwach Birmingham. W styczniu po przybyciu Roberta Halla z West Hamu – Redmond został odsunięty od składu. Nowy menedżer Lee Clark stwierdził, że musi bardziej przykładać się do treningów i dawać z siebie 100%. Po rozmowie z trenerem zaakceptował całą sytuację i wysłuchał jego rad. W grudniu zagrał jako drugi napastnik obok Nikoli Žigicia.