Brancaleone Grillo, ambasciatore del papa e del re di Spagna, costruisce il palazzo a metà del XV secolo sul luogo dove si trova una domus magna della famiglia. È un edificio di grandi dimensioni rispetto ai canoni della Genova tardomedievale e inedito per la scelta di ricucire le case attorno ad un cortile angolare. Secondo Alizeri il portale con il bassorilievo raffigurante San Giorgio e il drago fu commissionato proprio in quegli anni ai fratelli Gagini. Acquistato nel 1496 da Luca Spinola, entrerà nei rolli di Genova dal 1576 con Nicolò Spinola. L'espansione del piano nobile su vico delle Mele e gli affreschi degli appartamenti (in parte scialbati) ad opera di Luca Cambiaso, "Nozze di Amore e Psiche" e "Augusto assiso in trono" e di Lazzaro Tavarone, "Mosè con gli Ebrei nel deserto", trasformano l'immagine del palazzo.