In the famous DS9 episode Trials and Tribble-ations we see the Department of Temporal Investigations asks some questions of Sisko and his recent unexpected time travel. What would they do in the event that a paradox was created, unless they had time travel abilities which, as far as is known through the series, is not yet discovered and used until about the 26th century (A Matter of Time - TNG), suggesting they come from the future and could create a paradox themselves!
There are several episodes of TOS, notably Assignment: Earth, that show the ability of Star Fleet to travel back in time at will during the 23rd century. One would assume that 24th century technology makes this even easier. So while it might be difficult for the Department of Temporal Investigations to deal with a time paradox if said paradox wiped them out or went unnoticed, in the event of a well-documented episode like Trials and Tribble-ations or Assignment: Earth, they'd have the option of going back and fixing things.