This order is correct. While the common order of French sentences is Subject - Verb - Complement, here is one of the cases where the opposite order is possible, especially in a literary context.
As Christophe rightly points, there is a difference between au premier coup and du premier coup.
Here the sentence has a more than likely implicit part:
Au premier coup [de hache] ne tombe pas l'arbre.
i.e. "with a single [axe] hit, the tree doesn't fall down" or "on the first [axe] hit, the tree doesn't fall down."
The verb is intransitive and the first clause is an indirect object or circumstantial.
See this page that gives some examples like:
Autour de l’arbre s’était enroulé un chèvrefeuille
vs
Un chèvrefeuille s’était enroulé autour de l'arbre
and
Une heure plus tard se produisit un évènement imprévu
vs
Un événement imprévu se produisit une heure plus tard