When I am saying that Evolution is not an empirical science I am not discussing the sequence of species found in the fossil record. Rather I am most specifically referring to the naturalistic explanation of how and why this came about. It is this part of the theory that is untestable and therefore not an empirical science. This does not mean that it is not a proper science, only that it is a speculative one, not an empirical one. Speculation and conjecture are a necessary part of the scientific endeavor. Indeed, without them science could not advance. Natural Evolution should just be honest about the limits of its study and the speculative nature of its conclusions.
The naturalistic explaination (I assume you are refering to natural selection and mutation) provides a number of constraints, wheras alternative explainations do not. One key constraint is that a new type of animal can only be derived from one existing type. So a new species of mammal cannot be built by taking parts from bats, birds and lizard for example. If an example of such a thing was found in the fossil record it would falsify the explaination.
The constraint also produces a tree of descent. If the fossil record did not match a tree of descent then that would falsify the explaination. For example finding a modern mammal fossil in the cambrian would falsify the mammal tree of descent, and through that falsify the explaination that mammals descended via the natural mechanisms of evolution.
Also the tree of descent implies a nested heirarchy of presnet day life. If genetic comparisons of living species do not fit a nested heirarchy then that would falsify the explaination.
There are many other ways that evolution can be tested, for example the naturalistic explaination puts the constraint that new types of animal must originate in the same location as the type they derived from. So the theory would not be compatible with indigenous elephants on hawaii.