Il palazzo si trova in via della Vigna Nuova, di fronte all'omonima piazzetta triangolare, caratterizzata dalla Loggia che pure porta il nome di questa importante famiglia fiorentina imparentata con i Medici e amica del padre di Leonardo.
Fu edificato alla metà del Quattrocento da Bernardo Rossellino su disegno dell'Alberti per Giovanni Rucellai, il cui nome deriva da "oricello", colorante violetto ricavato dai licheni, che veniva impiegato per tingere i tessuti ed era prodotto in via degli Orti Oricellari.
Lo stile di questo palazzo ispirò l’architettura di alcuni dei principali palazzi fiorentini della seconda metà del Quattrocento, giungendo ad influenzare anche il palazzo Piccolomini progettato da Bernardo Rossellino a Pienza. L’unico ingegno idraulico progettato da Leonardo, di cui è finora documentata la realizzazione, è il contatore d’acqua che egli avrebbe inviato dalla Francia a Bernardo Rucellai, come attesta il manoscritto di Lorenzo e Benvenuto della Volpaia conservato nella Biblioteca Marciana di Venezia.