A plow will go deeper than a tiller. We (my dad and I- he is more into gardening than I am) plow, then disc. I then till it up, right when we are ready to plant. It means changing some implements (actually, using two tractors- he plows and discs with his NH3930, then I till), but it produces a beautiful product, and it is easier on the tiller.
I have also tilled up gardens that were plowed, which worked fine. It is rougher on my little B7100 and myself, but it works.
I have also tilled up virgin ground, which also worked, but I think would have worked better if plowed and disced first.