In the Star Wars movies, we first hear the name "Sidious" used in The Phantom Menace (referring, of course, to Palpatine). Did this name appear earlier in any other media, or was that name created solely for the prequel trilogy?
The name Sidious was first used (and first appeared) in Star Wars: The Phantom Menace. It doesn't appear in any earlier Star Wars script, nor in any of the Original Trilogy novelisations written prior to 2014.
Specifically, its first use was in the Terry Brooks novelisation of The Phantom Menace which came out several hours before the film's premiere on the 19th May, 1999.
Gunray made a placating gesture. “Stay calm! I’ll wager the Senate is completely unaware of the supreme chancellor’s moves in this matter. Go. Distract them while I contact Lord Sidious.”
Prior to the film's release the name of Darth Sidious was mentioned in various press articles; a powerful and mysterious character whose power was only exceeded by his mystery.
Darth Sidious (Episode 1). This Sith Lord stays in the shadows as Maul's Mentor. His plan is to take over the republic.