A trianoni békeszerződés által Romániához csatolt egykori Temes vármegyében született, szülőfalujának román neve Becicherecu Mic. Apja, Gyenes József húsipari szakmunkás volt, anyját Kovács Júliának hívták. Teljes neve: Gyenes András Károly.
Két középiskolai osztályt végzett, majd 1937-ben hentestanulónak állt Temesvárott. 1940-es felszabadulása után kisebb üzletekben dolgozott segédként. 1943 elején
átszökött Magyarországra. Illegális határátlépőként Losoncra internálták, de néhány
hét múlva elengedték, s még az év májusában a szegedi Pick-gyárban helyezkedett el
szakmájában.
1944 őszén, a front átvonulása után belépett a húsosok szakszervezetébe, 1945-
ben a kommunista pártba. A Pick-gyárban az üzemi bizottság egyik alapítója és 1946.
februárig tagja, majd 1947-ig munkahelyi párttitkár volt. 1947. decemberben a szegedi
szakmaközi bizottság iskolájának vezetője, 1948. májusban a Magyarországi Húsipari
Munkások Szabad Szakszervezete oktatási titkára, egyúttal a szakszervezet központi
vezetőségének tagja lett. 1948. augusztusban a Szakszervezeti Tanács (1948. októbertől Szakszervezetek Országos Tanácsa) Káderosztályára került politikai munkatársnak.
1949. októberben az MDP öt hónapos pártiskolájára küldték hallgatónak, 1950. márciustól ugyanott az iskola tanáraként működött. 1950. októbertől az immár iparági alapon átszervezett, érdekképviseleti szerepétől megfosztott szakszervezeti mozgalomban az Élelmezési Dolgozók Szakszervezetének főtitkárhelyetteseként, 1951. áprilistól főtitkáraként tevékenykedett. 1953. februártól a SZOT Káderosztályát vezette, 1954.
augusztustól 1955. februárig a SZOT titkáraként a szervezet egyik első embere volt.
1955-től a Szovjetunió Kommunista Pártja Központi Bizottsága hároméves pártfőiskoláján tanult. Az 1956-os forradalom hírére hazatért, november 10-én kormánybiztosként Nógrád megyébe küldték, majd megbízták az 1956. október vége óta átmenetileg Magyar Szabad Szakszervezetek Országos Szövetsége néven működő SZOT
Sportosztályának vezetésével. 1958. januárban a Magyar Testnevelési és Sporthivatal
(az elnevezés még abban az évben Magyar Testnevelési és Sporttanácsra változott)
elnökhelyettesének nevezték ki.
1961. novemberben a „sporthivatalban elkövetett hibák miatt” a Központi Ellenőrző
Bizottság megrovás pártbüntetésben részesítette, s mivel oroszul, románul és németül
is jól beszélt 1962. februártól a Magyar Szocialista Munkáspárt Központi Bizottsága
Külügyi Osztálya alosztályvezetőjeként „külügyi vonalra irányították át”. 1963. májusban osztályvezető-helyettessé nevezték ki, 1968. júniusban Puja Frigyest követte az
osztályvezetői székben. 1970. februártól külügyminiszter-helyettes, majd 1971. április
végétől ismét a KB Külügyi Osztályának vezetője volt. 1974. júniusban helyét Berecz
Jánosnak kellett átengednie, s augusztusban a (kelet-)berlini nagykövetség élére állították. Az MSZMP XI. kongresszusán (1975. március 17–22.) a KB és a KB Titkárságának
tagjává választották, s átvette külügyi KB-titkári posztot, amelyet Komócsin Zoltán
betegsége, majd halála miatt ideiglenesen Pullai Árpád töltött be. Ugyanakkor az állampárt legfőbb irányító testületébe, a Politikai Bizottságba sem akkor, sem később
nem került be, így szerepe elsősorban a döntések előkészítésére és végrehajtására
korlátozódott.
1982. júniusban Brutyó János utódaként a Központi Ellenőrzési Bizottság elnökévé
tették meg (1970–1975 között már egyszer a testület tagja volt), ezzel – bár a PB ülésein, ahogyan KB-titkárként, tanácskozási joggal továbbra is részt vehetett – még inkább
kiszorult a hatalom felső köreiből. 1989. áprilisban nyugdíjba vonult, októberben 1980-
tól folyamatos parlamenti mandátumától és az Élelmezésipari Dolgozók Szakszervezetében 1985-től betöltött elnöki tisztétől is megvált.