At the start of the show, Garak's been exiled from Cardassian space, and was left on Deep Space 9. I don't think the reason for this exile was ever explained. It seemed to be a genuine exile, and not some sort of deep cover spy mission, given the episodes where Garak joins back up with the Obsidian Order and his mentor, Enabran Tain. So, why was he exiled?
Reasons for his exile are not clear. However in the year 2368, Garak somehow betrayed Enabran Tain, and Tain ordered him killed. Garak escaped, but was exiled from his homeworld of Cardassia Prime.
Terok Nor seems a logical place to go. It was at that time a Cardassian space station while being away from the homeworld.
Also official Star Trek website says "he was forced to betray"
Garak was exiled after being forced even to betray his father/mentor, and they parted bitterly. In fact, Tain refused to give his son any forgiveness when he died alongside Garak in a Dominion prison camp in 2373
However "A Stitch In Time" a novel written by Andrew J. Robinson explores a lot more about Garak. The reason seems he was exiled for having an affair with a high ranking Gul's wife. When Tain found out about Elim and Palandines relationship, he ordered Garak to end it immediately, and never see Palandine again. Garak went to see her anyway, and was captured by Lokar. The resulting confrontation ended with Lokar's death.
Tain saw Garak's disobedience as a betrayal, and did nothing to help him with his resulting legal troubles. Garak was exiled from Cardassia, never to return on the pain of death. Garak, being the true loyal Cardassian he has always been actually believes he deserves exile. He said he was willing to give up everything and defy the military and the state for his own selfish desires.
Bashir: What I want to know is, out of all the stories you told me which ones were true and which ones weren't?
Garak: My dear doctor...they're all true.
Bashir: Even the lies?
Garak: Especially the lies.
As Memory Alpha makes clear:
In 2368, Garak somehow betrayed Tain, and Tain ordered him killed. Garak escaped, but was exiled from his homeworld of Cardassia Prime.
While suffering from the degradation of his cranial implant, he gave three versions of the reason for his exile to Doctor Julian Bashir:
- He first claimed he was a Gul in the Cardassian Mechanized Infantry and was exiled for killing several Cardassians, including his first officer, a man named Elim, as well as the daughter of a prominent military official, who were on board a transport going from Bajor to space station Terok Nor, when he destroyed it. Garak thought he was in fact killing members of the Bajoran Resistance who were planning to sabotage Terok Nor.
- He then changed his story to say that as he and his assistant Elim were interrogating a group of Bajoran children he felt pity for them and let them go instead of turning them over to be executed. He was exiled when Elim turned him in to the authorities.
- Garak also said that he was exiled after being framed by his best friend Elim with evidence that a member of the Obsidian Order was allowing Bajoran prisoners to escape.
Dr. Bashir later discovered from Enabran Tain that "Elim" was actually Garak's first name, indicating that none of these explanations were entirely true.
It is simply part of the fun that no-one really knows the truth. But as Garak says: "The truth is usually just an excuse for lack of imagination."
I don't think the explanation from "A Stitch In Time" is well... Garak enough. The three explanations perhaps lead on into something even deeper; something darker. I think it is something to do with betraying Tain or so, but we won't find out, thanks to the man who's shrouded in mystery. Memory Alpha- as stated above -also says forced to betray Tain. Perhaps the Order might have had something against their former head, and the only way they could get to him was through his son, even though Tain didn't acknowledge Garak as a son until his dying breath.
Garak was always loyal to Tain above anyone else. Maybe his betrayal of Tain was an attempt to protect him in some way. Maybe he killed an important Cardassian who had evidence or the intent to bring Tain down, and Tain being as short-sighted as he is saw this as a betrayal and didn't hear Garak out.
Garak was the son of Tain and was said to be the next leader of the obsidian order, Garak told Bashir. Tain said on many occasions he should have killed Elim along time ago because he was Tain's biggest danger. Tain had Garak exiled from Cardassia to keep him from taking over as leader because Tain never trusted his son. Cardassian father's are proud of their kids taking power but that doesn't mean Tain was going to allow him the chance to kill him when he takes power since the only way to be the most powerful person in the obsidian order is to kill the current most powerful that would be Tain as long as he is alive.
Rewatching the series, there are a number of subtle clues as to why Garak was exiled and not simply executed. His stories were obvious fabrications, which would have had him executed, saving tax evasion (hard labor). However, there a some small clues about his demeanor and physical actions and reactions that suggest that he was a member of the dissident movement. This primarily comes from the episode on DS9 with the students (because I love Cardassia), and the interactions with Entek on Cardassia 4. While Ghemor warns Kira about Garak, Tain's weakness for Garak manifested then in him saving Garak from execution or even a public trial. Garak's stories were too public to be covered up and would have had him killed. However, for the son of the head of Obsidian Order, called the Son of Tain while never acknowledged, to be a dissident would require both that he not be killed nor imprisoned, which would tarnish everything Tain did, and that he be exiled from Cardassia to avoid him fomenting more dissidence. Garak often remarks on his friends on Cardassia, usually suggesting that the Order was searching for them, already. His invocation of his father was his betrayal of Tain, but he felt that he never actually betrayed Tain because he didn't betray Cardassia in his mind. Thus, Mila maintained his innocence, and Tain distanced himself from Garak, including going into an early retirement. An interesting coincidence is that Garak was exiled from Cardassia the same year that Procal Dukat was tried and executed, suggesting a connection there, which would explain Tekeny Ghemor's warning to Kira about Garak doing anything to save himself and advance his own agenda.