The earliest use of "de Brahe" I have found is in a letter in German dated 26 July 1589, by one of Brahe's royal admirers, William IV, Landgrave of Hesse (1532-1592), reprinted by Brahe in his Epistolarum astronomicarum libri : quorum primus hic ... principis Gulielmi Hassiae Landtgrauij ac ipsius mathematici literas, unaque responsa ad singulas complectitur. The copy of the book linked here was printed in 1610, but the same letter appears in a 1596 edition. (For those who have trouble reading the old German type, the next page has a translation into Latin.) William wrote "zu dem Tychoni de Brahe", where the syntax of the sentence puts the name in the dative case. ("Zu" implies dative in German; the dative form of the Latin name "Tycho" is "Tychoni".) As Stephan Mattheisen points out, the words "Tychoni de Brahe" are in Latin, set in Roman type, the rest of the sentence is in German, set in German type. The Latin word "de" means "from", the equivalent of German "von".
The other letters in this book show Tycho's usual signature was "Tycho Brahe", so in a sense William's use of "de Brahe" is a mistake. But not so serious a mistake as to prevent Tycho from reprinting it verbatim in this collection of letters.
Google Books shows many pre 1700 instances of "de Brahe", often in German. I ran across an instance in the 1680 Leipzig Cometischer Gedenkzettel
by Christianus Uranophilus. He reports "Anno 1590, gedencket Tycho de Brahe eines Cometens. In diesem Jahre ist an vielen Orten grosse Hungersnoth gewesen" (="In 1590 TdB observed a comet. In that year great famine occurred in many places.")
The same method turned up multiple instances of "de Brahe" in a 1594 collection of Anacreontic verse, Columbae Poeticae by Friedrich Taubmann, a professor at Wittenberg. This book is discussed in a modern work, that I wish I could understand better. It seems possible to me that Taubmann used "de Brahe" to fit the meter of his verse form.