Tài năng của một nhà cầm quân lớn bắt đầu bộc lộ ở Tolbukhin vào mùa đông năm 1942 tại Stalingrad. Đây là khoảng thời gian Hồng quân phát động chiến dịch Sao Thiên vương, bao vây chặt cụm quân 330.000 người của Đức quốc xã, đánh bại mọi nỗ lực của quân Đức nhằm giải vây cho cánh quân này.
Trên cương vị Tư lệnh Tập đoàn quân (TĐQ) 57 thuộc Phương diện quân (PDQ) Stalingrad, Tolbukhin đã hoàn thành xuất sắc nhiệm vụ, được đánh giá rất cao về khả năng tổ chức và tài năng quân sự.
Từ cuối tháng 8/1943, Tolbukhin trên cương vị Tư lệnh PDQ Ukraine 4, cùng các PDQ Belorussia do Đại tướng Rokossovsky làm Tư lệnh, PDQ Ukraine 1 do Đại tướng Vatutin làm Tư lệnh, PDQ Ukraine 2 do Thượng tướng Konev làm Tư lệnh, và PDQ Ukraine 3 do Đại tướng Manilovsky làm Tư lệnh tham gia chiến dịch tấn công Dnepr.
Mục tiêu là giải phóng, thu hồi vùng Donbass và cả vùng công nông nghiệp ở trung lưu và hạ lưu sông Đông-một trong những nguồn cung cấp lúa mì, quặng sắt, than đá cho nền kinh tế và công nghiệp quốc phòng.
Đến cuối tháng 12/1943, trận vượt sông Dnepr kết thúc. Hồng quân giải phóng hoàn toàn lãnh thổ phía bờ trái, đứng vững chân trên một vùng rộng vài trăm km, sâu hơn 100km bên bờ phải sông Dnepr trong đó có Kiev, cắt rời và cô lập lực lượng Đức tại Crưm. Với kết cục này, việc quân Đức mất toàn bộ Ukraine và Crưm vào tay Hồng quân chỉ còn là vấn đề thời gian ngắn.
Từ tháng 5/1944, Tolbukhin chuyển sang làm Tư lệnh PDQ Ukraine 3, cùng PDQ Ukraine 2 của Nguyên soái Malinovsky tham gia chiến dịch Jassy-Kishinev. Kết thúc thắng lợi chiến dịch này, cuối năm 1944, trong khi PDQ Ukraine 2 tấn công vòng qua dãy núi Nam Carpath để tiến ra đồng bằng Hungary, thì PDQ Ukraine 3 được giao nhiệm vụ phối hợp với Quân giải phóng nhân dân Nam Tư (NOVJ) tấn công quân Đức tại Nam Tư.
Đây là hoạt động quân sự lớn nhất tại Nam Tư trong Thế chiến thứ hai, chiến dịch có sự phối hợp tác chiến lớn nhất giữa Hồng quân Liên Xô và NOVJ, đồng thời là một trong những chiến dịch quan trọng nhất tại khu vực Balkan năm 1944.
Kết thúc chiến dịch (từ 28/9 đến 10/10/1944), liên quân Liên Xô-NOVJ đánh tan 55.000 quân của TĐQ Serbia (Đức) và một số đơn vị quân ngụy Serbia, quân ngụy Nam Tư, chỉ khoảng gần 10.000 quân Đức và quân ngụy Nam Tư đóng tại Beograd thoát khỏi thành phố này trong tình trạng hỗn loạn và vô tổ chức.
Ngày 13/10, tướng Đức quốc xã Willi Schneckenburger, chỉ huy Cụm quân phòng thủ Beograd tử trận. Ngày 18/ 10, tướng Walter von Grabenhofen, chỉ huy Cụm tác chiến quân đoàn Stettner (Đức) cũng tử trận. Hồng quân Xô và NOVJ đều đạt được các mục tiêu chiến lược của mình là giải phóng thủ đô Nam Tư và tiến ra tuyến sông Sava.
Đối với Hồng quân Liên Xô, chiếm được Beograd không chỉ đơn giản là việc loại khỏi vòng chiến đấu một cụm tác chiến lớn của quân đội Đức quốc xã trên hướng Nam Tư mà còn mở ra con đường tiếp cận đồng bằng Hungary từ phía nam, để từ đó, các PDQ Ukraine 2 và 3 có thể trực tiếp phối hợp với nhau trong chiến dịch Budapest sắp tới theo kế hoạch đã được đại bản doanh vạch ra.
Với việc Beograd được giải phóng, uy tín của quân đội và Nhà nước Liên Xô được nâng cao hơn trong con mắt người dân Nam Tư nói riêng và người dân Balkan nói chung.
Sau khi giải phóng Beograd, Tolbukhin chỉ huy PDQ của mình tham gia chiến dịch Budapest từ giai đoạn 3 (diễn ra từ ngày 3/12/1944). Đây là một chiến dịch phức tạp và khó khăn đối với Hồng quân tại Trung Âu.
Chiến dịch kéo dài gần 4 tháng kể từ ngày 29/10/1944 cho đến lúc toàn bộ số quân Đức và Hungary còn sống sót tại Budapest hạ vũ khí đầu hàng ngày 13/2/1945. Thắng lợi của chiến dịch đã loại bỏ đồng minh cuối cùng của Đức ở châu Âu, mở ra cơ hội kết thúc Chiến tranh Thế giới thứ hai trong một tương lai gần.
Sau chiến tranh, Tolbukhin giữ chức Tổng tư lệnh các LLVT phía Nam bao gồm cả khu vực Balkan. Tháng 1/1947, ông về nước làm Tư lệnh Quân khu Zakavkaz cho đến khi mất vào ngày 17/10/1949.
Fyodor Ivanovich Tolbukhin được coi là một trong những tướng lĩnh Hồng quân xuất sắc nhất trong Thế chiến thứ hai. Tỉ mỉ, cẩn thận, ông được cấp dưới rất tôn trọng, nhất là vì ông luôn cố gắng hạn chế thương vong cho bộ đội ở mức thấp.
Nguyên soái Tolbukhin là một trong số ít tướng lĩnh Xô-viết được tặng thưởng huân chương Chiến thắng-huân chương cao quý nhất chỉ dành cho những nhà cầm quân xuất sắc.
Ông cũng được Chính phủ Nam Tư và Hungary phong tặng danh hiệu Anh hùng do có công trong việc tham gia giải phóng các nước này. Tên Tolbukhin từng được đặt cho thành phố Dobrich của Bulgary, một con phố chính của thành phố Beograd (Nam Tư) và một con đường ở thành phố Odessa. Một đài tưởng niệm cũng được dựng lên tại quê hương ông Yaroslavl.
