Pierwszego gola w Scottish Premier League Miller strzelił 18 października 2003 w meczu z Hearts. Na listę strzelców wpisał się w 9 minucie spotkania po podaniu Stilijana Petrowa, a w 50 minucie zdobył swoją drugą bramkę ustalając wynik meczu na 5:0. Po tym, jak Miller strzelił gola w pojedynku z Olympiquem Lyon, Martin O’Neill zaoferował irlandzkiemu zawodnikowi długoterminowy kontrakt w celu zatrzymania go w Celticu na dłużej.

Manchester United Miller nie przedłużył ostatecznie umowy z Celtikiem i 1 lipca 2004 odszedł do Manchesteru United, z którym jeszcze w styczniu tego samego roku podpisał przedterminową umowę. Opuszczenie Glasgow przez Irlandczyka zostało odebrane przez kibiców Celticu jako obraza klubu i brak lojalności, bowiem Celtic pomógł Millerowi w wyleczeniu poważnej kontuzji, której nabawił się na początku kariery. Miller strzelił swojego pierwszego gola dla Manchesteru 26 października w spotkaniu Pucharu Ligi Angielskiej przeciwko Crewe Alexandra. Na początku pobytu w ekipie „Czerwonych Diabłów” irlandzki pomocnik regularnie dostawał szanse występów, jednak pod koniec sezonu 2005/2006 rzadko kiedy pojawiał się na boisku. We wszystkich rozgrywkach Miller rozegrał dla Manchesteru łącznie 22 mecze.