Grečko se narodil v roce 1903 v Godolajevce u Rostova. V roce 1936 absolvoval vojenskou Frunzeho akademii a v roce 1941 Akademii generálního štábu. První velitelskou funkci zastával od podzimu 1941 jako velitel 34. jezdecké divize a později jezdecké skupiny Jihozápadního frontu, se kterou se zúčastnil ústupových bojů v roce 1941. V lednu 1942 byl jmenován velitelem 5. jezdeckého sboru v řadách Jižního frontu. Od dubna do srpna 1942 velel 12. armádě, která bojovala v Donbasu a na severním Kavkazu.

Od září do prosince 1942 velel 47. armádě a později 18. armádě bojující v oblasti Novorossijska a Tuapse. V lednu 1943 byl jmenován velitelem 56. armády osvobozující Kavkaz. V říjnu 1943 byl jmenován zástupcem velitele 1. ukrajinského frontu, se kterým se podílel na osvobozování Kyjeva a Lvova. Koncem války velel 1. gardové armádě, která osvobozovala Československo. Po skončení 2. světové války byl v letech 1960 – 1967 vrchním velitelem spojených armád Varšavské smlouvy. Andrej Grečko zemřel v Moskvě v roce 1976.