The earliest high-profile “native ad” I know of happened in 1831, when Alexander Pushkin released “Evgeny Onegin”. This is a very big deal. Russian Empire had huge cultural influence back then, and it was fashionable. Everything coming from it was cool. Sobranie London still has Russian Empire coat of arms as their logo. Also, Pushkin is regarded by many to be the best Russian poet ever, with Evgeny Onegin being his flagship masterpiece.

So, Breguet, the watch company, decided to advertise in this very piece. It went like this (sorry for the lack of rhyme and the overall lameness in my translation, it is hardly possible to translate Russian poetry to English):

Wearing a wide bolivar hat,
Onegin is going to the avenue
He's chilling there until
Breguet that never sleeps
Chimes him that it is time
To go and get something to eat

To put it into a context, it's as if someone bought an ad in Romeo and Juliet.