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.

Diritto:
1. Il Tribunale federale si pronuncia d'ufficio e con pieno potere d'esame sulla propria competenza e sull'ammissibilità del rimedio esperito (art. 29 cpv. 1 LTF; <ref-ruling> consid. 1.1 pag. 3).
Interposto tempestivamente (art. 100 cpv. 1 LTF) dalle parti soccombenti in sede cantonale (art. 76 cpv. 1 lett. a LTF) contro una decisione finale (art. 90 LTF) pronunciata dall'autorità ticinese di ultima istanza (art. 75 cpv. 1 LTF) in una causa civile di carattere pecuniario il cui valore litigioso supera fr. 30'000.-- (art. 74 cpv. 1 let. b LTF) il ricorso risulta ricevibile, perlomeno sotto questo profilo.
2. Prima di chinarsi sulle censure ricorsuali, considerato il loro tenore, appare opportuno rammentare i principi che reggono il rimedio esperito.
2.1 Con il ricorso in materia civile può essere fatta valere la violazione del diritto federale (art. 95 lett. a LTF) che include anche i diritti costituzionali (<ref-ruling> consid. 3.1, 462 consid. 2.3).
2.2 Il Tribunale federale esamina d'ufficio l'applicazione del diritto federale (art. 106 cpv. 1 LTF). Non è vincolato né dagli argomenti sollevati nel ricorso né dai motivi addotti dall'autorità inferiore, può accogliere un ricorso per motivi diversi da quelli invocati dalla parte insorgente e respingerlo adottando un'argomentazione differente da quella esposta nel giudizio impugnato (cfr. <ref-ruling> consid. 4.3.4 pag. 241). Ciononostante, tenuto conto dell'onere di allegazione e motivazione posto dall'art. 42 cpv. 1 e 2 LTF, che non ossequiato comporta l'inammissibilità del gravame (art. 108 cpv. 1 lett. b LTF), il Tribunale federale esamina di regola solo le censure sollevate (<ref-ruling> consid. 2 pag. 550; <ref-ruling> consid. 1.4.1 pag. 254). Nel ricorso è dunque necessario spiegare in maniera concisa perché l'atto impugnato viola il diritto federale e la motivazione dev'essere riferita all'oggetto del litigio, in modo che si capisca perché e su quali punti la decisione viene contestata (<ref-ruling> consid. 2.1).
Le esigenze di motivazione quando viene fatta valere la violazione di diritti fondamentali e di disposizioni di diritto cantonale e intercantonale sono più rigorose.
Il Tribunale federale tratta infatti queste censure solo se la parte ricorrente le ha debitamente sollevate e motivate, come prescritto dall'art. 106 cpv. 2 LTF (<ref-ruling> consid. 2.2). Il campo di applicazione di questa norma corrisponde a quello del precedente ricorso di diritto pubblico per violazione dei diritti costituzionali (<ref-ruling> consid. 6 pag. 397, 638 consid. 2) e valgono pertanto le regole di motivazione poste dall'art. 90 cpv. 1 lett. b OG (cfr. <ref-ruling> consid. 1.3 pag. 261 seg.).
2.3 In linea di principio, il Tribunale federale fonda inoltre il suo ragionamento giuridico sull'accertamento dei fatti svolto dall'autorità inferiore (art. 105 cpv. 1 LTF); può scostarsene o completarlo solo se è stato svolto in modo manifestamente inesatto o in violazione del diritto ai sensi dell'art. 95 LTF (art. 105 cpv. 2 LTF). L'accertamento dei fatti contenuto nella sentenza impugnata può essere censurato alle stesse condizioni; occorre inoltre che l'eliminazione dell'asserito vizio possa influire in maniera determinante sull'esito della causa (art. 97 cpv. 1 LTF).
Tocca alla parte che propone una fattispecie diversa da quella contenuta nella sentenza criticata il compito di esporre in maniera circostanziata il motivo che la induce a ritenere adempiute queste condizioni (art. 97 cpv. 1 LTF).
2.3.1 La definizione di "manifestamente inesatto" corrisponde a quella di arbitrario (DTF <ref-ruling> consid. 1.2.2 pag. 252) e configura dunque a sua volta una violazione di un diritto fondamentale (art. 9 Cost.; <ref-ruling> consid. 1.4.1 pag. 39). La corrispondente censura deve pertanto ossequiare i requisiti di motivazione posti dall'art. 106 cpv. 2 LTF. Secondo costante giurisprudenza, il ricorrente che lamenta una violazione del divieto d'arbitrio nell'accertamento dei fatti e nell'apprezzamento delle prove non può limitarsi a criticare la decisione impugnata come in una procedura d'appello, dove l'autorità di ricorso gode di cognizione libera, opponendo semplicemente la propria opinione a quella dell'autorità cantonale, bensì deve dimostrare, attraverso un'argomentazione chiara e dettagliata, che la decisione impugnata si fonda su un apprezzamento delle prove manifestamente insostenibile (<ref-ruling> consid. 4.1 pag. 589; <ref-ruling> consid. 1.3 pag. 262).
2.3.2 La violazione del diritto ai sensi dell'art. 95 LTF può risiedere in una fattispecie incompleta, poiché l'autorità inferiore viola il diritto materiale se non accerta tutti i fatti pertinenti alla sua applicazione.
Se intende completare l'accertamento dei fatti per ottenere una corretta applicazione del diritto, il ricorrente deve tuttavia indicare di aver già allegato le circostanze di fatto addotte nel gravame in sede cantonale, nei modi e nei tempi previsti dalle disposizioni procedurali applicabili e di aver fornito i relativi mezzi di prova (Messaggio concernente la revisione totale dell'organizzazione giudiziaria federale del 28 febbraio 2001, FF 2001 pag. 3894 e 3899).
2.3.3 Per il resto, dinanzi al Tribunale federale possono essere addotti nuovi fatti e nuovi mezzi di prova soltanto se ne dà motivo la decisione dell'autorità inferiore (art. 99 cpv. 1 LTF; cfr. <ref-ruling> consid. 3).
3. Considerato il domicilio italiano dei ricorrenti, la controversia presenta un aspetto internazionale, che impone al Tribunale federale di verificare d'ufficio e con pieno potere d'esame il diritto applicabile (<ref-ruling> consid. 2 con rinvii).
Giusta l'art. 116 cpv. 1 LDIP il contratto è regolato dal diritto scelto dalle parti. Se le parti non hanno scelto il diritto applicabile, il contratto è regolato dal diritto dello Stato con il quale è più strettamente connesso (art. 117 cpv. 1 LDIP), ovvero quello in cui la parte che deve eseguire la prestazione caratteristica ha la dimora abituale o la stabile organizzazione (art. 117 cpv. 2 LDIP).
In concreto, non è dato di sapere se le parti - che, come l'autorità giudiziaria ticinese, danno per scontata l'applicabilità del diritto federale privato svizzero - abbiano operato una scelta di diritto a favore di questa normativa. Sia come sia, anche in assenza di una simile scelta torna senz'altro applicabile il diritto elvetico, visto che nei contratti di mandato e di prestazione di servizi la "prestazione caratteristica" è la prestazione del servizio (art. 117 cpv. 3 lett. c LDIP), che in concreto è stata fornita da una banca con sede in Svizzera.
4. Nella sentenza impugnata il Tribunale d'appello ha negato ai ricorrenti il diritto di esigere il risarcimento dell'asserito pregiudizio subito dalla relazione bancaria intestata alla società panamense per il motivo che l'unica persona legittimata ad avanzare pretese in merito a tale relazione bancaria è, appunto, la società panamense.
Se il giudizio cantonale su tale questione dovesse risultare conforme al diritto federale, diverrebbe superfluo chinarsi sulle censure ricorsuali concernenti l'asserita responsabilità contrattuale (art. 398 CO) e/o extracontrattuale (art. 55 CO) dell'opponente per il comportamento del suo dipendente.
Occorre pertanto innanzitutto stabilire se la Corte ticinese ha a ragione escluso la legittimazione attiva dei ricorrenti.
5. La legittimazione attiva (o qualità per agire) si definisce come il diritto di far valere una certa pretesa in una procedura giudiziaria; il riconoscimento della legittimazione attiva significa, in un procedimento civile, che la parte attrice può far valere la sua pretesa contro la parte convenuta (Fabienne Hohl, Procédure civile, vol. I, 2001, n. 433).
La legittimazione attiva spetta di principio al titolare della pretesa litigiosa (<ref-ruling> consid. 3) e viene determinata secondo il diritto applicabile al merito; il suo difetto conduce alla reiezione dell'azione, indipendentemente dalla realizzazione degli elementi oggettivi della pretesa litigiosa (<ref-ruling> consid. 1 pag. 63).
Incombe alla parte attrice apportare la prova delle circostanze che dimostrano la sua legittimazione attiva (<ref-ruling> consid. 3.1 pag. 424).
6. In ingresso all'esame della legittimazione attiva dei ricorrenti, il Tribunale d'appello ha negato loro la possibilità di trarre vantaggio dalla sentenza penale di condanna pronunciata nei confronti di D._ il 26 marzo 2008, con la quale egli è stato obbligato a versar loro tutta una serie di importi a titolo di risarcimento danni.
A prescindere dal fatto che tale documento è stato prodotto alla II Camera civile solo in modo informale, i giudici ticinesi hanno rammentato che, giusta l'art. 112 cpv. 1 CPC/TI, la sentenza penale vincola il giudice civile solo per l'accertamento del fatto che ha costituito oggetto del giudizio penale, "per cui la decisione con cui a quel momento il funzionario è stato condannato a rimborsare gli attori [qui ricorrenti], oltretutto non motivata su quella particolare questione, non implica la loro legittimazione attiva nella causa da loro promossa contro la banca, che non era la loro controparte nella sede penale".
A mente dei ricorrenti tale decisione viola l'art. 41 segg., in particolare gli art. 53 e 55 CO.
6.1 L'art. 53 CO, applicabile all'insieme del diritto privato (DTF 66 II 80 consid. 1 pag. 83), stabilisce che, nel giudizio circa l'esistenza o la non esistenza della colpa e la capacità o l'incapacità di discernimento, il giudice civile non è vincolato dalle disposizioni del diritto penale che regolano l'imputabilità né da un giudizio di assoluzione (cpv. 1); egli non è vincolato dalla sentenza penale nemmeno nel giudizio circa l'apprezzamento della colpa e la determinazione del danno (cpv. 2).
La giurisprudenza ravvede in questa norma un'ingerenza del legislatore federale nella competenza dei Cantoni di definire il diritto processuale, limitatamente alla questione della colpa e della determinazione del danno; in questi due ambiti, nell'interesse del diritto materiale federale, è stato escluso un vincolo del giudice civile a una precedente pronunzia penale. In altre parole, quando decide sulla responsabilità, il giudice civile deve, in virtù del diritto federale, pronunciarsi sull'apprezzamento della colpa e sulla determinazione del danno, senza tener conto di una sentenza penale intervenuta in precedenza. Per il rimanente, il legislatore cantonale è libero di prevedere che il giudice civile sia vincolato dalla sentenza penale, in particolare per quel che concerne l'accertamento del fatto che ha costituito oggetto del giudizio penale e del suo carattere illecito (<ref-ruling> consid. 3 con rinvii).
6.2 In concreto, non risulta che la Corte cantonale abbia violato il citato disposto federale, né i ricorrenti forniscono alcuna spiegazione precisa al riguardo.
Essi non censurano adeguatamente nemmeno l'applicazione dell'art. 112 CPC/TI, che potrebbe essere rivista solo sotto il ristretto profilo dell'arbitrio (<ref-ruling> consid. 2.3 pag. 466; cfr. quanto esposto al consid. 2). È vero che giusta questa norma, come detto, la sentenza penale vincola il giudice civile per l'accertamento del fatto che ha costituito oggetto del giudizio penale, ma i ricorrenti nemmeno indicano quale sarebbe il fatto accertato e che ha costituito oggetto del giudizio penale che i giudici del Tribunale d'appello avrebbero arbitrariamente omesso di considerare ai fini del loro giudizio. Essi non possono limitarsi a richiamare la decisione di riconoscere loro la qualità di parte civile nel quadro del procedimento penale, visto che tale riconoscimento non poggia unicamente su di un accertamento di fatto ma anche su di un apprezzamento giuridico e che, in ogni caso, nell'ambito del procedimento penale sono state esaminate anche operazioni che il funzionario aveva eseguito su conti intestati personalmente ai ricorrenti.
Per lo stesso motivo non può essere di nessun soccorso nemmeno la sentenza emanata dal Tribunale federale il 1° giugno 2007 nella causa 4C.5/2007; anche in quel caso, infatti, il litigio verteva su di una relazione bancaria intestata a uno dei ricorrenti personalmente e non a una società terza.
7. Il Tribunale d'appello ha ritenuto che - evidenziando di essere non solo gli aventi diritto economico dei beni depositati sul conto ma anche gli unici azionisti della titolare del conto - i ricorrenti abbiano implicitamente voluto affermare di essere loro i veri titolari dei diritti spettanti alla società panamense, in base al principio della trasparenza (Durchgriff).
Dopo aver rammentato il carattere eccezionale di questo principio, i giudici ticinesi hanno negato di poterlo applicare alla fattispecie in rassegna. Non si può infatti ritenere che il richiamo all'autonomia giuridica della società panamense da parte della banca sia costitutivo di un abuso di diritto. Anche se l'interposizione di questa entità giuridica era stata proposta dall'istituto di credito, questa soluzione era stata adottata nell'interesse dai qui ricorrenti, i quali intendevano così salvaguardare le loro esigenze di discrezione ed evitare eventuali problemi ereditari. Nulla muta - hanno proseguito i magistrati cantonali - il fatto che nel contratto fiduciario con F._SA essi si siano riservati, per quanto concerneva la gestione patrimoniale dei conti della società, la facoltà di dare direttamente e congiuntamente istruzioni alla banca. Innanzitutto non risulta che ciò sia mai avvenuto e, secondariamente, questa pattuizione non vincolava la banca; ma anche se l'avesse vincolata, non sarebbe stata sufficiente per far nascere un rapporto contrattuale diretto fra lei e i ricorrenti, i quali avrebbero piuttosto agito in veste di procuratori o mandatari di fatto sul conto, senza influire sulla titolarità dello stesso, "che le parti avevano liberamente e concordemente voluto attribuire, per le loro particolari esigenze, proprio a una terza entità giuridica".
7.1 I ricorrenti ravvedono invece un abuso di diritto nell'agire della banca opponente, che vuole mantere la finzione dell'esistenza della persona giuridica, allorché fu proprio lei a voler l'interposizione della società panamense, "accampando motivazioni di carattere ereditario per gli ignari ricorrenti".
Sia come sia, per i ricorrenti, la figura giuridica del Durchgriff non si attaglia alla fattispecie e ribadiscono ancora una volta l'esistenza di un rapporto contrattuale diretto fra loro e la banca opponente, "rapporto relativo esclusivamente alla gestione patrimoniale degli averi intestati formalmente a E._Inc., ma gestiti nell'ambito di un contratto diretto" fra la banca e loro.
7.2 Con questi argomenti i ricorrenti ripropongono in pratica la loro lettura della controversia, senza confrontarsi con gli argomenti giuridici posti a fondamento della decisione impugnata. Essi si discostano anche, senza criticarla apertamente, dalla fattispecie accertata in sede cantonale, ad esempio quando si dicono "ignari" delle ragioni ereditarie che hanno portato all'intestazione dei loro beni alla società panamense. Per dimostrare l'esistenza di un rapporto di mandato di gestione patrimoniale fra loro e la banca, si richiamano inoltre a circostanze contenute negli atti del procedimento penale, senza nemmeno indicare dove e quando se ne sarebbero già prevalsi in sede cantonale.
Così come formulata la censura non ossequia i requisiti di motivazione esposti al consid. 2.
7.3 A ogni modo la sentenza impugnata è conforme al diritto federale.
I ricorrenti non contestano l'accertamento secondo il quale l'intestazione dei beni alla società panamense, seppur proposta dalla banca, è avvenuta con il loro consenso. Non risulta d'altro canto ch'essi abbiano mai fatto valere un vizio di volontà a questo riguardo. Come rettamente osservato dai giudici ticinesi, il fatto che sia stata la banca a proporre questa soluzione, non ne inficia la validità, tanto più ch'essa - stando a quanto accertato in maniera vincolante per il Tribunale federale, vista l'assenza di un'adeguata contestazione - corrispondeva ai bisogni e alla volontà dei ricorrenti. In siffatte circostanze, la banca poteva legittimamente ritenersi contrattualmente vincolata solo alla società panamense e riconoscere solo ad essa la posizione di creditore, con i relativi diritti, perlomeno fino al momento in cui non le fosse stato presentato un valido atto di cessione da E._Inc. ai ricorrenti. Il fatto che i ricorrenti fossero gli aventi diritto economico dei beni depositati sul conto bancario intestato a questa società, le cui azioni erano tutte nelle loro mani, induce infatti a qualificarla quale loro rappresentante indiretta nei confronti della banca (Gauch/Schluep/ Schmid, Schweizerisches Obligationenrecht, Allgemeiner Teil, vol. I, 9a ed., n. 1025 pag. 221). La rappresentanza indiretta - che si verifica appunto quando una persona agisce a nome proprio, ma per conto di un altro - non ha nessun effetto immediato sul "rappresentato"; il contratto vincola unicamente le parti contraenti. In questo caso il rappresentante funge da "prestanome" e agisce "fiduciariamente" per il "rappresentato", il quale può acquisire i diritti derivanti dal contratto solamente mediante una cessione del credito - secondo i principi che reggono questo atto - dopo la stipulazione del contratto (art. 32 cpv. 3 CO). Se ne deve concludere che la banca opponente può a ragione considerare che solo la società panamense avesse diritto di disporre sugli averi depositati sul conto e, di conseguenza, pretendere il risarcimento del danno patito a causa di eventuali malversazioni eseguite da D._ rispettivamente, più in generale, a causa di operazioni finanziarie in contrasto con la strategia d'investimento pattuita o con gli obblighi di diligenza tipici della banca. Ed è altrettanto a ragione che la banca opponente si richiama al principio della responsabilità civile secondo cui danneggiato è solo colui che subisce direttamente un danno nel suo patrimonio, mentre il terzo che patisce un pregiudizio solamente a causa di una sua particolare relazione con il danneggiato diretto, ovvero un danno riflesso rispettivamente un danno indiretto, non può avanzare alcuna pretesa di risarcimento (<ref-ruling> consid. 3.1.1 con rinvii).
8. Da tutto quanto esposto discende la reiezione del ricorso nella misura in cui è ammissibile.
Le spese giudiziarie e le ripetibili seguono la soccombenza (art. 66 cpv. 1 e 5 e 68 cpv. 1, 2 e 4 LTF).

Per questi motivi, il Tribunale federale pronuncia:
1. Nella misura in cui è ammissibile, il ricorso è respinto.
2. Le spese giudiziarie di fr. 20'000.-- sono poste a carico dei ricorrenti, in solido, con l'obbligo di rifondere all'opponente, sempre con vincolo di solidarietà, fr. 22'000.-- a titolo di ripetibili della sede federale.
3. Comunicazione ai patrocinatori delle parti e alla II Camera civile del Tribunale d'appello del Cantone Ticino.