One context where tracking the passage of time overnight was extremely important was in the convents of late antique and medieval Europe. Monastic life generally prescribes periods of prayer at set times throughout the day, including overnight.

It's clear from many sources that the primary means of keeping track overnight was to watch the stars! Monks and nuns (our sources are monastic) knew which constellations' rising and falling times to look for at different points of the year.

There is less information about what to do when it was cloudy, as it can often be in Europe. Peter Damian, a theologian and sundry Church roles of the 11C, writes that when the stars are not visible, the "marker of the hours" (a monk with that role, often the sacristan) must chant psalms to keep track of the time.

I don't know how this would have played out in other context, though. Hourglasses are not introduced into the west until quite late, the 14th century or so. We know of some monasteries that had water clocks, but that doesn't seem to have been a standard (and even those houses were obliged to watch the stars).