Po regularnych występach w klubie z Pizy, włodarze Genoi zdecydowali że w sezonie 1992/93 Andrea będzie występował w ekipie Rossoblu. Grał tam między innymi z inną wschodzącą gwiazdą piłki nożnej, Christianem Panucci. W swoim pierwszym sezonie w Serie A Fortunato grał na tyle dobrze, że zwrócił uwagę ówczesnego trenera Juventusu, Giovanniego Trapattoniego, który sprowadził go do ekipy Bianconerich. W Juve młody obrońca otrzymał biało-czarną koszulkę z numerem 3, należącym w latach 80. do znakomitego lewego obrońcy Antionio Cabriniego.
Znakiem firmowym Fortunato były częste rajdy lewą stroną boiska i dokładne podania lewą nogą, które docierały m.in. na głowy Roberto Baggio i Gianluci Vialli. Czuł się on częścią drużyny nie tylko na boisku, ale także poza nim. Jego osobisty urok i osobowość sprawiły, że zaskarbił sobie sympatię wielu osób. Wśród nich był także Arrigo Sacchi, ówczesny trener reprezentacji narodowej Włoch, który nazwał go "objawieniem włoskiego futbolu" i powołał zawodnika Juventusu na jego - jak się później okazało - jedyny mecz w Squadra Azzurra. Było to spotkanie z Estonią, 22 września 1993 w Tallinnie. Fortunato zajął miejsce Paolo Maldiniego i grał wspólnie z Franco Baresim w wygranym przez Włochów 3-0 meczu.