Some of the initial efforts didn't go so well.
He didn't impress Upaka on the road, for example: http://www.accesstoinsight.org/tipitaka ... .than.html
To set rolling the wheel of Dhamma I go to the city of Kasi. In a world become blind, I beat the drum of the Deathless.'
"'From your claims, my friend, you must be an infinite conqueror.'
'Conquerors are those like me who have reached fermentations' end. I've conquered evil qualities, and so, Upaka, I'm a conqueror.'
"When this was said, Upaka said, 'May it be so, my friend,' and — shaking his head, taking a side-road — he left.
When he first approached the 5 ascetics, he also didn't do so well: http://www.accesstoinsight.org/tipitaka ... .than.html
"So I said to them, 'Don't address the Tathagata by name and as "friend." The Tathagata, friends, is a worthy one, rightly self-awakened. Lend ear, friends: the Deathless has been attained. I will instruct you. I will teach you the Dhamma. Practicing as instructed, you will in no long time reach & remain in the supreme goal of the holy life for which clansmen rightly go forth from home into homelessness, knowing & realizing it for yourselves in the here & now.'
"When this was said, the group of five monks replied to me, 'By that practice, that conduct, that performance of austerities you did not attain any superior human states, any distinction in knowledge & vision worthy of a noble one. So how can you now — living luxuriously, straying from your exertion, backsliding into abundance — have attained any superior human states, any distinction in knowledge & vision worthy of a noble one?'
But he subsequently persuaded them:
"And so I was able to convince them. I would teach two monks while three went for alms, and we six lived off what the three brought back from their alms round. Then I would teach three monks while two went for alms, and we six lived off what the two brought back from their alms round. Then the group of five monks — thus exhorted, thus instructed by me — being subject themselves to birth, seeing the drawbacks of birth, seeking the unborn, unexcelled rest from the yoke, Unbinding, reached the unborn, unexcelled rest from the yoke: Unbinding. Being subject themselves to aging... illness... death... sorrow... defilement, seeing the drawbacks of aging... illness... death... sorrow... defilement, seeking the aging-less, illness-less, deathless, sorrow-less, unexcelled rest from the yoke, Unbinding, they reached the aging-less, illness-less, deathless, sorrow-less, unexcelled rest from the yoke: Unbinding. Knowledge & vision arose in them: 'Unprovoked is our release. This is the last birth. There is now no further becoming.'
In the commentary to the Fire Sermon, SN 35.28http://www.accesstoinsight.org/tipitaka ... .than.html
It is said that the Buddha first tried to convert Kassapa with his powers, conquering a serpent: http://www.theravada-dhamma.org/pdf/Ana ... Sermon.pdf
In the morning the Blessed One showed the dead body of the fiery fiend to Kassapa,
"His fire has been conquered by my fire."
And Kassapa thought to himself.
"Sakyamuni is a great samana and possesses high powers, but he is not holy
However, he did convert Kassapa and his group with the subsequent Fire Sermon.
So you could argue (I think I heard this from a Patrick Kearny talk) that the Buddha initially tried to teach by just proclaiming his superiority, or demonstrating his powers, but had to work out how to do it a bit more subtly as he went along...