His political career started in the then-ruling Socialist Unity Party (SED) of East Germany, to which he was admitted in 1967. In 1971 he became a licensed attorney, and during the 1970s and 1980s defended several notable dissidents, including Rudolf Bahro, Robert Havemann, Ulrike Poppe, and Bärbel Bohley.
In the late 1980s he began to emerge as one of East Germany's leading reformists within the SED. In 1989, he and a group of lawyers presented a counter-draft to the government's Travel Bill, which authorized mass public demonstrations. This led to a rally on November 4 in which he spoke and called for various reforms, including free elections. In December of 1989, he became a member of a special SED party session investigating official corruption and abuse of power.
In his role as a reformist he led the transformation of the SED into a more democratic socialist party; initially renamed the Socialist Unity Party - Party of Democratic Socialism (SED-PDS), it later became simply the Party of Democratic Socialism (PDS), and he served as its chairman starting in 1990. In May 1990 he was elected to the Volkskammer in the first free election of that body, and served there until it was dissolved upon German reunification on October 3, 1990. In the first post-unification all-Germany elections, he was elected to the Bundestag, and served there until 2000. He remained chairman of the PDS through 1998, and then from 1998 to 2000 served as chairman of the party's parliamentary group.
In 1992 allegations were brought against him of having been an unofficial member of East Germany's Ministry for State Security (the infamous Stasi). He denied these allegations, and the matter was largely dropped due to his parliamentary immunity. However, the allegations were raised again in 1996, and this time the Bundestag voted to revoke his immunity and proceed with an investigation. In 1998 the Bundestag's immunity committee concluded that Gysi had been a collaborator with the Stasi from 1978 to 1989, and fined him 8,000 Deutsche Marks (though the FDP and his own PDS disputed and voted against the verdict). Despite the affair, he retained his seat in the Bundestag in the 1998 elections.
In 2000 he resigned as chairman of the PDS's parliamentary group, but continued as an active member of the party. Following the victory in Berlin's 2001 municipal elections of a coalition of the PDS and the more moderate Social Democratic Party (SPD), he was appointed Deputy Mayor and Senator for Economics, Labor, and Women's Issues. In that role he has emphasized practical issues and advocated the reinstitution of some of what he sees as the better aspects of East Germany's system, such as extended child-care hours and a longer school day. He resigned July 31, 2002 as Deputy Major, Senator and Member of the Berlin Parliament.