Magic and Wisdom share a common root, but have since diverged. The Wise Man became the Wizard. The natural philosopher similarly diverged to beget the scientist and the alchemist. Our notion of magic, in the modern sense, is a product of that divergence.
The divergence occurred as we moved from a belief in a capricious universe, in which many things were animated by spirits of various characters, to belief in a deterministic materialist universe. The old stories, which, at their formation had been speculations about, or representation of, the apparent capriciousness of the world, now posited events that were outside the rules of the materialist universe. They were labeled "magic".
A fantasy, though, really requires only a world with a nature and laws different from our own. There need be no division between the natural and the magical in such a world. Just a different nature. It is only when we apply our beliefs about the nature and laws of the mundane universe we live in to these worlds that we label any non-deterministic events as "magic". Within the nature and laws of those worlds, they need be no more than the nature of the world itself: laws as iron as the laws of our world, but simply different.
You can write stories in those worlds without "magic", in the sense of any violation of the rules of that world. Tolkien's Middle Earth very much fits this mold. No one does "magic". But the laws and potentialities of that world are different.
The notion of "magic", as it seems to be commonly used today, posits first our deterministic universe, and then, somehow layered on top of this, a system of magic that allows people to violate the laws of this universe. This strikes me as a very different (and profoundly less interesting) thing that setting a story in a more spirit-infused world. Not that J.K. Rowling did not make billions doing exactly this. But it is still only one branch of fantastic literature, and, to my mind at least, an inferior one.
Can you write fantasy without magic? Centainly. Simply write a world that is "fantastic" compared to our own, and which obeys its own fantastic laws as strictly as ours obeys its dull and mundane ones.