Dobre występy jesienią 2000 roku spowodowały, iż Gavrančiciem zainteresowały się kluby z zachodniej Europy. Jednak zimą 2001 Gavrančić wybrał ofertę ukraińskiego Dynama Kijów, do którego ściągnął go słynny Walery Łobanowski sumę około 2 milionów euro. W rundzie wiosennej Gavrančić miał jednak problemy z wywalczeniem miejsca w składzie i rozegrał tylko 6 meczów ligowych, ale mógł czuć się po raz pierwszy w karierze mistrzem kraju. W sezonie 2001/2002 Dynamo nie zdołało wywalczyć prymatu na Ukrainie i musiało zadowolić się tytułem wicemistrza Ukrainy, a Goran przez pewien czas w ogóle nie pojawiał się na boisku z powodu kontuzji. Sezon 2002/2003 był dla kijowian dużo bardziej udany. Zdołali wywalczyć dublet, a Gavrančić rozegrał całkiem niezły sezon, zdobywając 4 gole w 23 ligowych meczach i został uznany najlepszym obrońcą ligi ukraińskiej. Także w kolejnym sezonie (2003/2004) Gavrančić z Dynamem mógł świętować mistrzostwo kraju i po raz drugi z rzędu reprezentował Dynamo w Lidze Mistrzów, jednak znów nie udało się wyjść klubowi z Kijowa z grupy. W sezonie 2004/2005 Gavrančić nie oddawał miejsca w składzie, ale mistrzem został tym razem konkurent Dynama, Szachtar Donieck. Na pocieszenie pozostało zdobycie Pucharu Ukrainy.