Nach dem Abitur am Gymnasium Oberalster in Hamburg absolvierte Lemke ein Lehramtsstudium der Erziehungs- und Sportwissenschaft an der Universität Hamburg, welches er mit dem ersten Staatsexamen beendete. Anschließend war er von 1971 bis 1974 als wissenschaftlicher Mitarbeiter an der Universität Bremen tätig. Nach dem Ende seiner Nebentätigkeit als Doppelagent für KGB und Verfassungsschutz übernahm er 1974 die Geschäftsführung des SPD-Landesverbandes Bremen, bis er 1981 als Manager zum Fußballverein Werder Bremen wechselte. Er blieb bis 1999 bei Werder Bremen und prägte gemeinsam mit Otto Rehhagel maßgeblich die „Goldenen“ 1980er und 1990er Jahre (1981 bis 1995) des Vereins, in denen der Verein einmal den Europacup gewinnen konnte, zweimal Deutscher Meister und dreimal Pokalsieger wurde. Lemke gehört seit 1999 dem Aufsichtsrat der Werder Bremen GmbH & Co KGaA an und ist seit 2005 auch Vorsitzender des Aufsichtsrates. Nach der Bürgerschaftswahl 1999 wurde Lemke am 7. Juli 1999 als Senator für Bildung und Wissenschaft in den von Senatspräsident Henning Scherf geleiteten Senat der Freien und Hansestadt Bremen gewählt. Nach der Wahl zur Bremischen Bürgerschaft 2007 übernahm Lemke in der neuen rot-grünen Koalition am 29. Juni 2007 das Amt des Senators für Inneres und Sport. Ende 2007 wurde Lemke von der Bundesregierung für das Amt des Sonderberaters für Sport und Entwicklung bei den Vereinten Nationen vorgeschlagen. Nachdem der Haushaltsausschuss des Deutschen Bundestages zugesichert hatte, die Finanzierung dieses Amtes in Höhe von jährlich 450.000 € zu übernehmen, wurde Lemke am 18. März 2008 von UN-Generalsekretär Ban Ki Moon als Nachfolger von Adolf Ogi berufen. Lemke trat deshalb am 6. April 2008 als Innensenator zurück. - Im Stadtgespräch nimmt er Stellung zu seinem Amtswechsel und spricht über seine Erwartungen und die berufliche und private Organisation seiner neuen Situation.