It became a monster hit and ended up being the most sold single in Sweden that year.
This was the start of an international career that continues almost 25 years later with 6 million record sales.
Ahead of this month's national Ultimate Wild tour, we catch up with one of the defining voices of the early '90s Eurodance movement.
Looking back at your first single release, 'Trust Me', what was your life like prior to the release?
[Pandora] I was 23-years old living on my own in Västerås. I studied French, maths, history and different subjects to make it to university when 'Trust Me' was released and changed my life forever.
I had no experience of tour life or the record business. I had done some live performances with different bands where I was the lead singer, but that's all.
After the song was released, the response was pretty epic; how did your life change once 'Trust Me' became so popular?
Well, suddenly people knew who I was. That was a very strange experience. I had no free time 'cause my career made me work most of the time.
I also travelled around the world singing my songs to people that knew them already. It was hard to figure out how that was possible.
The past decade or so; what have you been doing artistically?
Since 2000, I’ve released four albums ('Won’t Look Back, '9 Lives', 'United DJs vs Pandora' and 'Head Up High'). I’ve also recorded a self-written album under my real name Anne Li. It's not released yet. I'm touring all year 'round and most of my shows are in Finland and Sweden.
Sometimes I perform acoustic just me and my guitar singing Anne Li songs or 'Fields Of Gold' or other beautiful, slow songs that I love. I need the balance between up-tempo Pandora songs and the storytelling singer-songwriter 'me'.
You are headed to Australia as part of the Ultimate Wild tour; what can fans expect from you?
They can expect me to do the Australian hits, and an excited artist happy to see my fans again after so many years [away].
Your original background was more country and pop music; how did you end up becoming a techno, Eurodance singer?
Good question. I'm a 'yes sayer' and thought 'why not?' when I was asked to record the demos I’d been singing in a small studio in my former hometown Västerås. These demos ended up at EMI Sweden’s office and the rest is history.
When you began, Eurodance wasn't really a genre; compared to today's mainstream support of electronic music, what was it like as an electronic musician in the early '90s?
It was tough since we were not taken seriously by media. Also, because the genre was new people didn’t know how to react. 'What is this shit?' But then it kind of exploded and today I'm proud to be a pioneer of my genre.
You have sold six million records in your career; that is a staggering number. The support of the fans must be incredible to experience?
Yes, it's amazing that the fans are still there. I enjoy performing a lot more today than when it all began; I was young and nervous about not being good enough. Today, I can take a step back and let the audience sing for me.
You've no doubt had many, many great interactions with fans; any that stick out you can recount for us?
Yes, I have an Australian fan who came to see my shows in Finland. It ended up in a friendship and she came to my house helped me fix my garden and organise my gold discs on the wall for a photo shoot for a magazine called PLAZA.
What does it mean to still have an audience to sing your songs to, almost 25 years since your career started?
It means everything of course. I can’t perform if nobody wants to hear me. I hope my audience can really feel the love I'm feeling for them.
Away from music, what else occupies your time?
I have a huge garden and a passion for gardening. I also have a 13-year-old son that I love spending time with. I'm engaged to a Finnish man living in Helsinki, so it’s a lot of travelling between Sweden and Finland even apart from my shows there.
What about the 1990s did you most love… whether it be fashion, technology or something else?
The fashion and all the crazy hair styles.
The Ultimate Wild 2017 TourFeaturing Fragma, DJ Sammy, Alice DJ, Pandora, 666 and Nick Skitz
Fri Nov 17 - Eatons Hill Hotel (Brisbane)
Sat Nov 18 - Big Top Luna Park (Sydney)
Sat Nov 18 - Rooty Hill RSL (Sydney)
Fri Nov 19 - The Cambridge Hotel (Newcastle)
Fri Nov 24 - Trak Lounge (Melbourne)
Sat Nov 25 - Metro City (Perth)