Originariamente fu costruito nel Quattrocento per gli Alberti, che possedevano dal Trecento la maggior parte degli edifici su questo lato della strada, chiamata, non a caso, "Corso degli Alberti". Nel 1456 una serie di proprietà in questo sito venne venduta da Francesco di Altobianco Alberti a da Duccio di Noferi Mellini, esponente di una famiglia di mercanti originaria di Vicchio, che fin dagli anni ottanta del Trecento avevano partecipato attivamente alla vita politica della Repubblica e aveva anche donato alla vicina basilica di Santa Croce il pulpito di Benedetto da Maiano.
Tra la fine del Quattrocento e i primi del Cinquecento fu costruito l'attuale palazzo per volontà di Noferi di Duccio: per quanto una tradizione lo voglia su progetto di Michelangelo Buonarroti (negli interni un vano scale affiancato da due porte con un elaborato sistema di cornici in pietra serena mostrerebbe in effetti una certa analogia con un disegno dell'artista), presenta forme che rimandano sostanzialmente alle coeve architetture di Simone del Pollaiolo detto il Cronaca e di Baccio d'Agnolo. Completato verso il 1575 per volere di Domenico di Marco Mellini, modificando parzialmente il precedente impianto, il palazzo è stato successivamente proprietà di varie famiglie. Gli affreschi sulla facciata, peculiarità del palazzo, furono commissionati dai Mellini verso il 1575 al non altrimenti noto pittore e decoratore olandese Giovanni Stolf, su cartoni di Francesco Salviati; studi più recenti tuttavia riconducono questi affreschi a Jacopo Coppi, stabilendo anche che un "Giovanni Stolf" non sia mai esistito. Così come riporta Agostino Lapini nel suo Diario Fiorentino dal 1552 al 1596: «Et in questo 1575, pochi giorni innanzi la Festa di San Giovanni, si scoperse la prima facciata dipinta delle case in Firenze, che fu quella del Vigna, che è dei Nunziati artefici, e la seconda fu quella del Mellino da Santa Croce dove è la Storia di Perseo dipinta medesimamente con colori».
Il palazzo venne venduto per tremila scudi a Bernardo di ser Alessandro Guidi Arrighi nel 1634, e da allora cambiò diversi proprietari: i Quaratesi (1705), i Coppi (1842), i Lecchini e infine i Fossi (1890), tramite il marchese Federico, i cui discendenti lo posseggono tutt'oggi.
La decorazione della facciata, più volte segnalata dalla letteratura (assieme alla volta di un gabinetto terreno affrescato dallo stesso Salviati e a una statua di Esculapio del Giambologna posta a capo della scala), è rimasta a lungo occultata sotto uno spesso strato di sporco che la rendeva illeggibile. Nel 1938 fu imposto al marchese Federico Fossi il restauro del fronte, in occasione della venuta a Firenze di Hitler del maggio di quell'anno, ma per mancanza di fondi fu eseguita (fortunatamente, visti i limiti delle metodiche del tempo) solo una semplice spolveratura, che non migliorò di molto la situazione. Il sorprendente recupero del ciclo venne infine compiuto grazie ad un intervento di restauro eseguito tra il 1994 e il 1996 con la direzione del cantiere affidata all'ingegnere Rolando Chiodi (incaricato dalla proprietà che ha sostenuto gli ingenti costi dei lavori), il coordinamento di Andrea Todorow e la collaborazione e il supporto tecnico scientifico dell'Opificio delle Pietre Dure e della Soprintendenza per i Beni Ambientali e Architettonici di Firenze.
Ad oggi, purtroppo, la visibilità del ciclo pittorico risulta già parzialmente ridotta per le polveri depositatesi sulla superficie pittorica, e per gli altri fattori di degrado legati all'inquinamento ambientale della zona.
Il palazzo appare (come palazzo Coppi) nell'elenco redatto nel 1901 dalla Direzione Generale delle Antichità e Belle Arti, quale edificio monumentale da considerare patrimonio artistico nazionale, ed è sottoposto a vincolo architettonico dal 1936.
L'aspetto esterno del palazzo è solido, con panca di via, il portale e le finestre dei piani superiori riquadrate da uno spesso bugnato, mentre al pian terreno le aperture presentano cornici rettangolari più semplici. Il cornicione è uno dei più significativi esempi in città per la lavorazione e per l'aggetto.
Accanto al portale principale esiste una buchetta usata per vendere il vino, un'attività tipica delle grandi famiglie proprietarie di vigneti, che nei secoli precedenti vendevano direttamente dai loro palazzi tramite queste buche larghe appena da far passare una bottiglia.
Al 36 rosso si trova un edificio di pertinenza addossato, di quattro piani su due assi. In quanto destinato a locali di servizio, non presenta sul fronte elementi architettonici di particolare interesse. Si segnalano, nel locale al terreno adibito ad attività commerciale, porzioni a vista dell'originaria muratura medievale.
Affreschi della facciata
Gli affreschi ingentiliscono la facciata e sono divisi in tre fasce dalle cornici marcapiano. Essi, molto danneggiati dalle intemperie e dalle alluvioni (più di una soprattutto in questa zona), sono stati restaurati recentemente e riportati alla luce con risultati straordinari. La fascia al pian terreno al di sotto del livello dei davanzali delle finestre, è comunque irrimediabilmente svanita per colpa delle inondazioni, tra cui quella gravissima del 1966.
Il tema del ciclo, legato a complesse allegorie mitologiche, è noto grazie agli appunti raccolti nel Diario fiorentino di A. Lapini, che li descrisse nel 1596, e dalla menzione di G. Cinelli nelle Bellezze della città di Firenze (1677). Lapini non manca di ricordare come la facciata di palazzo Mellini fu la seconda in tutta Firenze a ricevere tale tipo di decorazione, preceduta solo da palazzo Nunzianti (1575).
Sono rappresentati un corteo di personaggi mitologici che rappresentano il mito di Danae e Perseo dalle Metamorfosi di Ovidio, dipinti secondo lo stile manierista.
A partire dall'ultimo piano, dove due putti nel sottogronda aprono teatralmente una tenda come per invitare i passanti ad assistere a una rappresentazione scenica, si vede un fregio con sei vasi da fiori alternati ad altrettanti medaglioni, con una serie di animali (pipistrello, pavone, Pegaso) ed oggetti simbolici o araldici (clava o pestello, scudo, teschio di cervo). Sempre nell'ultimo registro, ai lati delle finestre, si trovano sei figure dorate di poeti incoronati (o re) e una figura alata.
Nel registro mediano si dispiegano gli episodi delle storie di Perseo. Da sinistra si leggono:
Le bellezze della città di Firenze, dove a pieno di pittura, di scultura, di sacri templi, di palazzi, i più notabili artifizi, e più preziosi si contengono, scritte già da M. Francesco Bocchi, ed ora da M. Giovanni Cinelli ampliate, ed accresciute, Firenze, per Gio. Gugliantini, 1677, p. 307;
Federico Fantozzi, Nuova guida ovvero descrizione storico artistico critica della città e contorni di Firenze, Firenze, Giuseppe e fratelli Ducci, 1842, p. 232, n. 38;
Federico Fantozzi, Pianta geometrica della città di Firenze alla proporzione di 1 a 4500 levata dal vero e corredata di storiche annotazioni, Firenze, Galileiana, 1843, p. 163, n. 385;
Nuova guida della città di Firenze ossia descrizione di tutte le cose che vi si trovano degne d’osservazione, con piante e vedute, ultima edizione compilata da Giuseppe François, Firenze, Vincenzo Bulli, 1850, p. 212;
Ministero della Pubblica Istruzione (Direzione Generale delle Antichità e Belle Arti), Elenco degli Edifizi Monumentali in Italia, Roma, Tipografia ditta Ludovico Cecchini, 1902, p. 253;
L’illustratore fiorentino. Calendario storico per l’anno ..., a cura di Guido Carocci, Firenze, Tipografia Domenicana, 1904, pp. 22–25;
Janet Ross, Florentine Palace and their stories, with many illustrations by Adelaide Marchi, London, Dent, 1905, p. 105;
Walther Limburger, Die Gebäude von Florenz: Architekten, Strassen und Plätze in alphabetischen Verzeichnissen, Lipsia, F.A. Brockhaus, 1910, n. 457;
Augusto Garneri, Firenze e dintorni: in giro con un artista. Guida ricordo pratica storica critica, Torino et alt., Paravia & C., s.d. ma 1924, p. 148, n. XXXV;
Gunter Thiem, Christel Thiem, Toskanische Fassaden-Dekoration in Sgraffito und Fresko: 14. bis 17. Jahrhundert, München, Bruckmann, 1964, p. 141, n. 89, tav. 191;
Walther Limburger, Le costruzioni di Firenze, traduzione, aggiornamenti bibliografici e storici a cura di Mazzino Fossi, Firenze, Soprintendenza ai Monumenti di Firenze, 1968 (dattiloscritto presso la Biblioteca della Soprintendenza per i Beni Architettonici e per il Paesaggio per le province di Firenze Pistoia e Prato, 4/166), n. 457;
Leonardo Ginori Lisci, I palazzi di Firenze nella storia e nell’arte, Firenze, Giunti & Barbèra, 1972, II, pp. 633–634;
Piero Bargellini, Ennio Guarnieri, Le strade di Firenze, 4 voll., Firenze, Bonechi, 1977-1978, I, 1977, p. 119;
Marcello Vannucci, Splendidi palazzi di Firenze, con scritti di Janet Ross e Antonio Fredianelli, Firenze, Le Lettere, 1995, p. 130;
Cristina Danti et al., Il restauro della facciata dipinta da Giovanni Stalf su disegno di Francesco Salviati nel Palazzo Mellini Fossi a Firenze, in "OPD Restauro", 1997, 9, pp. 127–135;
Cristina Danti, Un'esperienza fiorentina di fissaggio della reintegrazione, in Feltre città dipinta, a cura di Giuliana Ericani, Treviso, Canova, 2001, pp. 191– 196;
Due restauri 2003, a cura di Patrizia Pietrogrande, Firenze, Centro Di per la Fondazione Giulio Marchi, 2003.
Touring Club Italiano, Firenze e provincia, Milano, Touring Editore, 2005, p. 411;
Eleonora Pecchioli, ‘Florentia Picta’. Le facciate dipinte e graffite dal XV al XX secolo, fotografie di Antonio Quattrone, Firenze, Centro Di, 2005, pp. 82–91;
Materiale informativo in loco, datato 13 novembre 2006.
Claudio Paolini, Case e palazzi nel quartiere di Santa Croce a Firenze, Firenze, Paideia, 2008, pp. 70–71, n. 80;
Claudio Paolini, Lungo le mura del secondo cerchio. Case e palazzi di via de’ Benci, Quaderni del Servizio Educativo della Soprintendenza BAPSAE per le province di Firenze Pistoia e Prato n. 25, Firenze, Polistampa, 2008, pp. 69–71, n. 17; p. 68, n. 16;
Claudio Paolini, Architetture fiorentine. Case e palazzi nel quartiere di Santa Croce, Firenze, Paideia, 2009, pp. 92–94, n. 96; p. 92, n. 95;
Toscana esclusiva, pubblicazione edita in occasione dell’iniziativa Lucca, Pisa, Siena: cortili e giardini aperti, Firenze: cortili e giardini aperti, 16 e 23 maggio 2010, a cura dell’Associazione Dimore Storiche Italiane, Sezione Toscana, testi a cura dell’Associazione Culturale Città Nascosta, Firenze, ADSI, 2010, pp. 47–48.