Of course, they also knew in the thirteenth century that the moon causes the tides, despite lacking Newtonian physics; Aquinas even occasionally points it out (e.g., "Take, for example, the ebb and flow of ocean tides, which result from the motion of the moon and change in accord with it" from De Motu Cordis). The person to whom the first suggestion of the moon's role is attributed is usually Pytheas of Massalia in the fourth century BC. We don't actually have any of Pytheas's written work on the ocean; and the references to the moon are fairly vague, so we don't exactly know what role he thought the moon played. Aristotle didn't know for sure (the Mediterranean has no observable tides, so they had little chance to observe them unless they traveled very widely indeed), but he knew that the tides occurred in Northern Europe, and says that some people ascribed them to the moon, although he himself never commits to this view. By the thirteenth century, it appears to have been the common view (apparently due to the influence of Albumazar, both directly in translation and indirectly through Robert Grosseteste) that the tides are caused by some sort of lunar influence, either an astrological sympathy broadly considered (the common view), or a form of light (Robert Grosseteste's suggestion, although he suggests a number of other factors), or a magnetic attraction (which is proposed by William of Auvergne in the De Universo), although there were still lots of things about the tides that were not understood (and were recognized as not being understood). David Edgar Cartwright's summary of Grosseteste's speculations on the tides is a good one for pretty much the whole period (Tides: A Scientific History, [Cambridge UP: 1999] p. 16):
The hypotheses included some ideas which have since been proven false, together with others which in essence have stood the test of time. Their real interest lies in the evident desire of the medieval philosophers to explain phenomena hitherto taken as granted, without calling on the supernatural, and their appreciation of what celestial configurations are important in controlling the tide. Such factors as lunar and solar longitude, lunar distance and declination, and the wind, are still essentially relevant in modern theory; only the medieval physics is inadequate.
I'm not sure they would have seen it as explaining "without calling on the supernatural"; what we call the 'supernatural' they would have taken to be always operative, so not appropriate for explaining the distinctive features of any phenomenon, unless you were claiming that it was miraculous. But it's true that they saw the tides as a natural phenomenon, and looked for an explanation in the natures of the things themselves.
You can find historical arguments for divine existence that make appeal to the tides, though; for instance, in Cicero's statement of the Stoic argument (De natura deorum, Book II, Section VII):
And the element which surpasses all these, I mean reason, and if we care to express it by a variety of terms, intelligence, design, reflection, foresight, where did we find, whence did we secure it? Shall the universe possess all other qualities, and not this one which is of most importance? Yet surely in all creation there is nothing nobler than the universe, nothing more excellent and more beautiful. There not only is not, but there cannot even be imagined anything nobler, and if reason and wisdom are the noblest of qualities, it is inevitable that they should exist in that which we acknowledge to be supremely noble. Again, who can help assenting to what I say when he considers the harmonious, concordant, and unbroken connection which there is in things? Would the earth be able to have one and the same time for flowering, and then again one and the same time in which it lies rough? Or could the approach and departure of the sun be known, at the time of the summer and winter solstice, by so many objects spontaneously changing? Or the tides of the sea, and of narrow straits, be affected by the rising or setting of the moon? Or the dissimilar movements of the planets be maintained by the one revolution of the whole sky? It would be certainly impossible for these things to come to pass in this way, with such mutual harmony amongst all parts of the universe, if they were not held together by one divine and all-pervading spirit.
Of course, the difference here is that the Stoic argument is pantheistic: it's an attempt to argue that the universe is God, so the argument here is not an appeal to the tides being otherwise inexplicable but instead to the fact that the tides are one of the many phenomena of the universe that clearly display some kind of order ("harmonious, concordant, and unbroken connection") and therefore something that can be identified as rational. And this is, of course, a structurally stronger and practically safer beginning for an argument: the tides obviously do exhibit a kind of order.