Fatti: A. Nell'autunno del 1992, a seguito del trasferimento del loro consulente bancario D._ alla succursale bellinzonese di C._, A.A._ e B.A._ hanno deciso di spostare i loro averi presso questo istituto bancario. Per ragioni di riservatezza ed esigenze ereditarie, così consigliati dalla banca, essi hanno però prima intestato i beni alla società panamense E._Inc. e conferito a F._SA, il mandato di amministrare e gestire questa società. Il 3 novembre 1992 E._Inc. ha dunque aperto un conto presso C._ di Bellinzona, conferendogli anche un mandato di gestione patrimoniale; nel relativo formulario A A.A._ e B.A._ sono stati indicati quali aventi diritto economico dei valori depositati. La relazione è stata chiusa il 12 settembre 1996. E._Inc. è stata sciolta e liquidata nel corso del 1999; i suoi attivi sono stati divisi in parti uguali fra A.A._ e B.A._. B. Successivamente si è appreso che D._ aveva effettuato operazioni non autorizzate su varie relazioni bancarie, appropriandosi di parte dei capitali. Nel dicembre 2001 è stato quindi avviato un procedimento penale nei suoi confronti che è sfociato, il 26 marzo 2008, in una sentenza di condanna. In questa egli è stato fra l'altro condannato a rimborsare varie somme ai fratelli A._, costituitisi parte civile nel procedimento penale. C. Nel frattempo, il 3 febbraio 2005 A.A._ e B.A._ hanno convenuto C._ dinanzi alla Pretura del Distretto di Bellinzona onde ottenere il risarcimento di fr. 4'668'039.--, pari alla perdita subita dalla relazione bancaria intestata alla società panamense tra il febbraio 1994 e il settembre 1996 a causa dell'agire di D._, il quale aveva a loro dire proceduto a investimenti speculativi che violavano il profilo d'investimento concordato ed effettuato tre prelevamenti non autorizzati. Aderendo all'eccezione di carenza di legittimazione attiva sollevata da C._, con sentenza del 4 aprile 2007 il Pretore ha integralmente respinto la petizione. Egli ha aggiunto che un'eventuale pretesa risarcitoria, da lui comunque negata in assenza di una violazione contrattuale o di un atto illecito imputabile alla banca, sarebbe stata in ogni caso prescritta. D. L'impugnativa interposta dai soccombenti contro questo giudizio è stata respinta dalla II Camera civile del Tribunale d'appello del Cantone Ticino il 17 luglio 2008. Pur dichiarandoli parzialmente irricevibili, siccome sollevati per la prima volta in sede di appello, la massima istanza cantonale ha disatteso nel merito tutti gli argomenti addotti da A.A._ e B.A._ a sostegno della loro legittimazione attiva. In breve, i giudici ticinesi hanno evidenziato che solo la società panamense potrebbe, se del caso, dirsi danneggiata dagli eventuali atti illeciti commessi da D._ in relazione alla gestione del conto a essa intestato; nella loro qualità di beneficiari economici A.A._ e B.A._ non possono vantare alcuna pretesa diretta. Nulla muta il fatto ch'essi fossero gli azionisti unici della società titolare del conto, autorizzati nel contempo a dare istruzioni alla banca. Nella fattispecie non sono infatti riuniti i presupposti per applicare il principio della trasparenza (Durchgriff) e ignorare l'indipendenza e l'autonomia sussistente tra la persona giuridica e le persone che la controllano e ne possiedono il capitale; in particolare non si può ritenere che il richiamo all'autonomia giuridica di E._Inc. da parte della banca configuri un abuso di diritto o una violazione del principio dell'affidamento o dell'interesse legittimo di un terzo. Infine - hanno concluso i magistrati cantonali - l'istruttoria non ha confermato la tesi secondo cui, sempre in relazione al medesimo conto, vi era un rapporto contrattuale diretto (di fatto) fra i fratelli A._ e la banca. E. L'11 settembre 2008 A.A._ e B.A._ sono insorti dinanzi al Tribunale federale con un ricorso in materia civile teso all'annullamento della pronunzia cantonale e alla sua riforma nel senso dell'integrale accoglimento della petizione. Nella risposta del 24 ottobre 2008 C._ ha proposto di respingere il gravame, mentre l'autorità cantonale ha rinunciato a formulare osservazioni.