The combinations of two particles(such as では, には, とは etc.) are often used to express the emphasis.
The upper one is translated as "I've never been to Tokyo before." And the lower one means basically the same but it implies "I've never been to Tokyo before but I've been to some other places in Japan."
As you say, without "は" is correct for sure, but with "は" it would be more precise to determine the place or time.
I hope it helps!! :)