Prior to 2372, Connelly, on Dayos IV, made a purchase with someone who had stolen their goods. Subsequently, Connelly spent two years in prison for dealing stolen goods on the planet. Later, he moved to Farius Prime, living on Jinami Street.
While on Farius Prime, Connelly became involved with the Orion Syndicate. He was unemployed and spent several weeks trying to find work. During this period, he frequented a bar which by "coincidence" was also frequented by Liam Bilby and his men. On one occasion, he witnessed one of his men, Krole, being spiked at a terminal in which he was using his dataport. Connelly stopped the others and successfully freed him, having recognized what was happening. The men were impressed, and, further, when Connelly implied he knew how to fix the dataport connection devices, Bilby convinced him to fix the devices for a reward the next day.
Connelly fixed the devices and returned to the next day. There, Bilby took Connelly to his home to reveal he'd looked into his background and found he was a man who had been "knocked around" for much of his life. He decided to reveal his allegiance to the Syndicate and give him another task, to fix some Klingon disruptors, in order to gain Bilby's trust and subsequently have a steady job with him. Connelly completed the job, though he was disturbed later when Bilby talked to the person who sold him the broken disruptors and killed him.
Bilby continued confiding with Connelly and even invited him to Earth to see his family. He even told Connelly about the Syndicate's Starfleet contact, to Connelly's surprise (and O'Brien's interest). He was later brought to a meeting with Raimus and Gelnon, a Vorta from the Dominion who wanted to meet Bilby. Upon seeing Connelly, Raimus questioned Bilby, but Bilby "witnessed" for him, settling the matter and solidifying the trust. They left after Gelnon said he wanted Bilby and his team to do something for him at a later time.
Connelly continued working for Bilby, breaking into the Bank of Bolias using his skills, and Bilby continued to trust him. Further, he told Connelly he would watch out for him, trusting him even more than Krole and Flith.
Connelly was with the group when Gelnon revealed the plan with the disruptors: to kill the Klingon ambassador, making it look like Gowron ordered it due to the ambassador's opposition to his alliance with the Federation. Connelly then worked with Bilby watching as he figured out a way to interrupt the embassy's power grid for a few seconds so Bilby's men could get in. It looked as if Connelly was not traced during this information gathering, but, later, Connelly tried to convince Bilby that that was a ruse, and that he shouldn't go through with the plan.