They didn't visit Paris before .
Hi, Yama. You need the perfect there. It can be either the present perfect ("They haven't visited Paris before") or the past perfect ("They hadn't visited Paris before"). To decide between the present and past perfect, you would need to be given some context. Probably the textbook wants you to choose the present perfect.
You can add "never" to the verb phrase: "They have/had never visited Paris before." You could not do that with the simple past. Even "didn't ever" wouldn't work: "They didn't ever visit Paris before." You would use "didn't visit Paris" with reference to an isolated trip on which they didn't visit that city. But "before" alerts you that the meaning calls for the perfect.
If "before" were being used as a subordinating conjunction followed by a clause, it would be possible to use the simple past. That is, it would be grammatical to say, "They didn't visit Paris before they got married." But that would suggest that they didn't make repeated trips to Paris together before they got married, not that they hadn't ever visited Paris before they got married.