In 1995, she gained the seat in the Perth and Kinross by-election succeeding the recently deceased Conservative MP, Sir Nicholas Fairbairn. She had initially been left off the SNP's candidate shortlist over her brief relationship in the 1970s with Donald Bain, then husband of SNP MP Margaret Ewing, on the grounds that the issue could prove an embarrassment to the party. Cunningham said the affair had begun after the couple had separated. She was put back in contention following an intervention by the then party leader Alex Salmond, and after Ewing made clear she had no objection to Cunningham's candidature. In the 1997 election, she stood for the Perth constituency and was elected.