1550s (n.), 1560s (adj.), from Prussia + -an. Prussian blue pigment (1724) came to English from French bleu de Prusse, so called for being discovered in Berlin, the Prussian capital.
All in all, it seems that Prussian blue was synthesised for the first time around 1706 by the Swiss immigrant Johann Jacob Diesbach in Berlin. [Jens Bartoll and Bärbel Jackisch, "Prussian Blue: A Chronology of the Early Years," in Zeitschrift für Kunsttechnologie und Konservierung 24, No. 1, 2010]
Early German sources refer to it as Preußisches Ultra-Marin and berliner blau. Prussic acid (1790), is from French acide prussique, so called in reference to prussian blue pigment, to which it is chemically related.