Il medievale Palazzo degli Anziani, dal primigenio aspetto turriforme, i cui resti sono visibili nella facciata su via Consoli del Mare, fu riattato e ricostruito da Giorgio Vasari su committenza del duca Cosimo I de’ Medici che, nel 1558, decise di fondare l’ordine di S. Stefano e di dare una sede alla milizia marinara. L’odierno nome di Palazzo della Carovana deriva dal corso di addestramento (la ‘carovana’) seguito dai cavalieri. Soltanto nel 1561 l’architetto fiorentino venne a Pisa per studiare l’aspetto della piazza e la disposizione dei vecchi edifici e, entro due anni, il palazzo ospitava già la milizia (1562-1564).
Vasari progettò un edificio regolare e unitario, ottenendo un effetto di simmetria e armonia in virtù dei decori pittorici e plastici che, ritmando la facciata con andamento modulare, nascondono le difformità delle vecchie strutture. Su disegno vasariano, Tommaso Battista del Verrocchio e Alessandro Forzori di Arezzo, eseguirono le pitture a graffito della facciata, oggi pesantemente rielaborata, al cui centro campeggia lo stemma mediceo-stefanino tra le allegorie della Religione e della Giustizia, opera di Stoldo Lorenzi (1563). Gli stemmi delle cantonate sono, invece, di Giovanni Fancelli (1564).
Nel 1821 fu costruita la scala marmorea a doppia rampa (in sostituzione della precedente) opera di Giuseppe Marchelli.
Nella parte alta della facciata, le nicchie ospitano i mezzibusti dei duchi medicei: Cosimo I, Francesco I e Ferdinando I realizzati dal 1590 al 1596 da Ridolfo Sirigatti, quello di Cosimo II del 1633 circa, opera dello scultore Pietro Tacca e, infine, quelli di Ferdinando II e Cosimo III, del 1681 e 1718, di mano di Giovan Battista Foggini.
Il palazzo, attuale sede della Scuola Normale Superiore, conserva al suo interno alcune sale decorate e dipinti cinquecenteschi.