A tehetséges hátvéd dobókézsége, ügyes passzai és atletikussága már NBA-karrierjének második évében All-Star helyet biztosított neki, azaz a ligaválogatott legjobb 10 játékosa közé került. 1990-ben az év középiskolás játékosának választották. A gimiben átlag 36,6 pontot dobott meccsenként. A Memphis Egyetemet választotta, de 1990-91-ben nem játszott. Első évében azonban máris a legjobbak között volt, az év játékosának jelölték és benne volt az év csapatában is. 1993-ban az NBA játékosbörzéjén a Golden State Warriors-hoz került, akik egyből elcserélték az Orlando Magic-hez, a csapathoz, amelyet még mindig erősít. Első évében már 16,0 pontos átlagot dobott meccsenként, Chris Webber után pedig ő lett az év második számú újonca. 1995-ben bekerült a liga All-Star válogatottjába, csapatát pedig első helyhez segítette a keleti mezőnyben. Jelölték az 1996-os Dream Teambe, ami az Atlantai Olimpián aratott győzelmet. Mivel ebben az évben Shaquille O’Neal, a csapat másik nagyágyúja eligazolt, Penny egyedül maradt Orlandoban, igazi sztárként. A következő szezonban egy sérülés miatt azonban több meccset is kihagyott, de ezután újult erővel visszatért, és azóta is az NBA egyik legmeghatározóbb játékosa, aki mellesleg a rajongó hölgyek egyik nagy kedvence is.
