Окончил Казанское высшее танковое командное училище (1969), Военную академию бронетанковых войск (1976), Военную академию Генерального штаба (1988).
Служил в танковых войсках на различных должностях. С 1994 года — командир 42-го Владикавказского армейского корпуса в Северо-Кавказском военном округе.
1995—1997 — командующий 58-й армией Северо-Кавказского военного округа. Во время Первой чеченской войны — командующий Объединённой группировкой войск Министерства обороны РФ в Чечне. Генерал-лейтенант (указ от 5 мая 1995 года).
В 1997 году назначен заместителем командующего Северо-Кавказским военным округом (СКВО).
В августе 1999 года возглавил группировку федеральных сил, отражавшую нападение боевиков на Дагестан. С началом Второй чеченской войны — командующий группировкой «Восток» Объединённых федеральных сил на Северном Кавказе.
С января 2000 года — первый заместитель командующего Объединённой группировкой федеральных сил на Северном Кавказе. Генерал-полковник (февраль 2000).
В апреле — июне 2000 года — командующий Объединённой группировкой федеральных сил на Северном Кавказе.
В мае 2000 — декабре 2002 г. г. — командующий войсками Северо-Кавказского военного округа СКВО.
В марте 2001 года поддержал во время суда Юрия Буданова, обвинявшегося в убийстве и изнасиловании чеченской девушки Эльзы Кунгаевой.
С февраля 2003 года — Советник Президента Российской Федерации (занимался вопросами казачества).
Действительный государственный советник Российской Федерации 2 класса (2008).
Погиб в авиакатастрофе самолёта Боинг-737-500 авиакомпании «Аэрофлот-Норд» в черте города Пермь, куда Геннадий Трошев летел на турнир по самбо, в 3 часа 11 минут (МСК) 14 сентября 2008 года. Похоронен в посёлке Северный, что под Краснодаром.
Улица Краснознамённая в Грозном переименована в улицу имени Геннадия Трошева.
Звезда Героя России (дубликат) и личные вещи генерала Трошева будут храниться в кадетской школе в якутском поселке Чернышевский, на открытии которой 1 сентября 2008 г. присутствовал генерал. После авиакатастрофы школе присвоено имя Трошева.
Именем Трошева назван 1-й Дагестанский кадетский корпус.
В Смоленске новая улица названа именем Трошева.
На Кубани именем генерала Трошева назвали Кропоткинский казачий кадетский корпус.
В Волгоградской области именем Трошева названа Самолшинская кадетская школа-интернат.
Именем Трошева назвали среднюю школу в Нальчике, в которой он учился с 1958 по 1965 годы. Решение об увековечивании памяти Трошева было принято советом местного самоуправления после того, как с соответствующей инициативой выступила администрация школы № 11, в которой был открыт музей генерал-полковника. Также городские власти переименовали Школьную улицу, расположенную рядом с учебным заведением, в улицу генерала Трошева. Кроме того, было решено установить мемориальную доску на доме № 136 по улице Иванова. Как отметили в пресс-службе администрации Нальчика, именно в этом доме жил Трошев.
На фасаде здания штаба Северо-Кавказского военного округа в Ростове-на-Дону установлена мемориальная доска Трошеву, кроме того, его именем будет названа одна из улиц района «Левенцовский», строящегося на западной окраине Ростова-на-Дону.
14 марта на Кубани учрежден фонд памяти Трошева — Некоммерческий фонд содействия развитию спорта и культуры «Дружбы народов Северного Кавказа» имени Героя России генерал-полковника Геннадия Николаевича Трошева. В Фонд вошли ветераны боевых действий, артисты, политики, которые поддерживают уставные цели и задачи фонда. Надежда Михайловна Трошева, мать Г. Н. Трошева, является председателем фонда.
Именем Трошева будет назван большой океанский морозильный траулер в Приморье, оснащенный современным технологическим оборудованием.
Траулер уже назван! "ГЕНЕРАЛ ТРОШЕВ", БМРТ типа "Пулковский Меридиан" пр.1288, порт приписки Находка, наименование судовладельца:ОАО "Преображенская база тралового флота"