How one can say that a date must happen before other date, for intance:
The X starting date should be prior to the Y starting date.
Is this sentence idiomatic or there is another way of stating that ?
There's certainly nothing wrong with using words like prior and precede in OP's context, but they're not exactly everyday language for the masses. In common parlance, people are much more likely to say something like...
In the world of project management, you would say
See this glossary of Project Management terms. (It does not define "depends upon" but rather uses it axiomatically.)
Depends upon would be stronger than the modal ("should be") that the OP employed. If you used the sentence above, you would be saying that the starting date of X must (not should) be prior to the starting date of Y.