Już w 1972 roku nawiązał współpracę z warszawskim klubem Stodoła, zakładając Trio Jazzowe z gitarzystą Krzysztofem Wolińskim oraz Januszem Osipowiczem, grającym na gitarze i flecie. Z grupy tej w roku 1974 wyłonił się duet gitar klasycznych Completorium (Andrzej Kleszczewski i Krzysztof Woliński). Artysta współpracował z zespołem do 1979 roku, dokonał nagrań dla radia, brał udział w festiwalach i konkursach jazzowych, zdobywając m. in. wyróżnienie na Studenckim Festiwalu Jazzowym „Jazz nad Odrą” we Wrocławiu (1975) i w Konkursie Jazzu Tradycyjnego „Złota Tarka” w Warszawie (1975 i 1978). Duet ten obył trzymiesięczne tournee po krajach byłego ZSRR, jako support zespołu Koman Band z wokalistką Krystyną Prońko.

Od 1979 Kleszczewski pracował w zespole Maryli Rodowicz jako gitarzysta i kompozytor. Odpowiadał za kierownictwo muzyczne nad jej projektem Święty spokój. Skomponował muzykę do takich piosenek w repertuarze Rodowicz, jak Zwierz ze Zgierza, Dentysta sadysta, Gdyby Zenek, Majaczek biedaczka i Napoleon nr 5. Piosenkę Dentysta sadysta nagrał również zespół Różowe Czuby, który wystąpił z tym utworem w kontrowersyjnym wówczas (i do dzisiaj budzącym emocje) teledysku. Utwór ten był na liście przebojów "Trójki" oraz zdobył pierwsze miejsce na telewizyjnej liście przebojów. Andrzej Kleszczewski był też członkiem zespołu instrumentalnego Maryli Rodowicz, który akompaniował w bardzo popularnym wówczas spektaklu Szalona lokomotywa w reżyserii Krzysztofa Jasińskiego, z udziałem takich artystów, jak m.in. Jerzy Stuhr, Halina Wyrodek, Zofia Niwińska, Marek Grechuta.

Następnie Andrzej Kleszczewski rozpoczął współpracę z zespołem znanego satyryka Krzysztofa Daukszewicza.

Skomponował również piosenkę Tato nie bój się dentysty do filmu o tym samym tytule w reż. Zofii Ołdak (1985).

Współpracował jako muzyk sesyjny z wieloma popularnymi polskimi zespołami i wykonawcami, m. in. z Grażyną Świtałą, Maciejem Pietrzykiem, Kapelą Warszawską. Wziął udział w nagraniu dwupłytowego albumu I Ching (1983), będącego autorskim przedsięwzięciem Zbigniewa Hołdysa.

Andrzej Kleszczewski jest autorem satyrycznych ilustracji do Pamiętnika IV Rzepy Krzysztofa Daukszewicza (2009).

aktualizacja: 2022 (wa)