Отец, Фердинанд Мюллер, был кожевенных дел мастером, владельцем кожевенного завода, председателем Баварского союза кожевников, а также депутатом Баварского ландтага от партии Центра. Мать, Виктория, урождённая Дойрингер, происходила из старинной семьи пивоваров. Был третьим ребёнком в семье (кроме Винценца в семье были старшая сестра Тереза, брат Ойген на пять лет старше его и младшая сестра Мария). Ещё трое детей умерли в младенчестве. Ойген стал католическим священником, Мария - врачом.
Первые классы начальной школы прошёл в Айхахе. Затем родители послали его в гуманитарную гиманзию в Меттен (Нижняя Бавария). В июле 1913 года он окончил её и 1 октября того же года поступил в 1-й (Баварский) сапёрный полк в Мюнхене в качестве добровольца-одногодичника. В январе 1914 года Мюллер перешёл в качестве фанен-юнкера в 13-й (вюртембергский) сапёрный батальон в Ульме. В мае 1914 года он в звании унтер-офицера был командирован в Королевское прусское военное училище в Касселе, где его и застало начало войны.
Некоторое время в августе 1914 года находился в запасном батальон в Ульме, пока в том же месяце не был отправлен в свой прежний батальон, расположенный в Вогезах. 6 сентября во время атаки получил слепое огнестрельное ранение в шею и был отправлен в госпиталь, в котором находился до ноября 1914 года.
В это же время ему присвоили звание лейтенанта. С 13 ноября 1914 года он снова находился в запасном батальоне в Ульме, а в декабре — на Западном фронте в составе 13 -го резервного батальона 14-го резервного армейского корпуса в районе Боном. В самом конце 1914 года Мюллера назначили командиром взвода в 1-ю резервную роту 28-й Баденской пехотной дивизии. В мае 1915 года в её составе участвовал в битве при Аррасе (отражение атак французского наступления).
В июне 1915 года Мюллер с повышением в чине до обер-лейтенанта в составе немецкого сапёрного отряда (250 человек) был отправлен в распоряжение германской военной миссии в Турцию. Участвовал в боях за Дарданеллы на юге полуострова в составе южной группы войск. В августе некоторое время находился в районе фронта при Айю-Бурну. В начале ноября был ранен английской гранатой и пролежал четыре недели в лазарете. В первой половине 1916 года проходил военно-географическую подготовку для действий в Месопотамии. В первой половине мая 1916 года Мюллер в составе сапёрного отряда был направлен в Месопотамию. В середине июня 1916 года отряд прибыл в Багдад.В июне-октябре 1916 года в составе 15-го турецкого сапёрного батальона в качестве командира роты участвовал в наступлении 13-го турецкого армейского корпуса на территорию Персии. В октябре 1916 года получил приказание вернуться в Германию (немецкий сапёрный отряд не находил должного применения). В конце ноября тяжело больной тифом и малярией Мюллер возвратился в Германию. Почти шесть месяцев находился в военном госпитале в Ульме.
Только в июле 1917 года был выписан из госпиталя и снова направлен в Турцию, на этот раз преподавателем в турецком военно-инженерном училище в Константинополе. В начале февраля 1918 года вернулся в Германию и был приписан к вюртембергскому сапёрному запасному батальону в Ульме. В июне 1918 года ему было присвоено звание обер-лейтенанта. В это время его переводят во 2-й гвардейский запасный сапёрный батальон в Берлин, который обеспечивал находящийся на Западном фронте гвардейский резервный инженерно-саперный полк, единственный огнеметный полк германской армии. Вскоре Мюллер прибыл в тыловой штаб этого полка в район Шарлевиля. В середине сентября 1918 года его назначают командовать 9-й сапёрной ротой в составе 7-й армии на фронте близ Эны. Во главе этой роты он встретил окончание Первой мировой войны 11 ноября 1918 года и вместе с ней был направлен в Берлин в середине декабря.
В январе 1919 года Мюллер поступил на службу в Пограничную стражу «Восток», первоначально служил в расформированном штабе 10-й армии адъютантом генерала инженерных войск Кане в Восточной Пруссии, а с февраля 1919 года был переведён в штаб командования Пограничной стражи Север, в марте участвовал в боях против остатков революционной народной морской дивизии в Кёнигсберге. С апреля 1919 года Мюллер служил офицером для поручений при начальнике оперативного отдела штаба командования Пограничной стражи Север барона фон Фрича, будущего командующего сухопутными войсками в 1930-е годы, а с осени — офицером для поручений при начальнике штаба. В феврале 1920 года командование Пограничной стражи было ликвидировано, и Мюллер во второй половине марта 1920 года стал командовать взводом в 13-м сапёрном батальоне рейхсвера в Ульме.
В 1921—1922 годах Мюллер проходил первый и второй курсы подготовки помощников командиров (как называлась в целях маскировки запрещенная Версальским договором высшая военная подготовка в Военной академии) в штабе 5-го военного округа в Штутгарте. Летом 1921 и 1922 годов офицеры, обучавшиеся на штутгартских курсах, в соответствии с общим порядком были направлены на три месяца в войска. В 1921 году Мюллер проходил службу в 1-м дивизионе 7-го (баварского) артиллерийского полка в Вюрцбурге. В его составе участвовал в дивизионных учениях в войсковом учебном лагере Графенвер. Летом 1922 года Мюллер был направлен на три месяца в 19-й (баварский) пехотный полк в Мюнхене. В начале октября 1922 года он возвратился в 5-й сапёрный батальон на должность командира взвода. В конце ноября 1923 года Мюллер был переведён в министерство рейхсвера в Берлин и до осени 1926 года работал офицером канцелярии майора, а чуть позже подполковника фон Шлейхера, начальника отдела Т-1-3 (военно-политический отдел).
24 сентября 1923 года Мюллер женился на 22-летней дочери адвоката Марии Брандль. 31 мая 1926 года у них родился сын Фридрих Фердинанд (в семье и среди друзей его звали Фриц). Впоследствии в 1944-1945 годах он служил в частях ПВО. После войны окончил Университет Гумбольдта. Женился на служащей государственной библиотеки ГДР Матильде Конрад.
С 1 октября 1926 года Мюллер был откомандирован для прохождения третьего и последнего года обучения на курсах помощников командиров при министерстве рейхсвера. В начале июня 1927 года он закончил курсы и два месяца после этого проходил стажировку в войсковых частях (четыре недели в 6-м батальоне связи в Ганновере и четыре недели в 6-м автобатальоне в Мюнстере). После этого Мюллер с октября 1927 года по сентябрь 1928 года был прикомандирован к военной секции Имперского архива. 1 октября 1928 года он снова был переведён на работу в военно политический отдел (возглавляемый Шлейхером) на должность референта. С 1929 до конца сентября 1931 года занимал в военно-политическом отделе должность референта по вопросам Пограничной стражи. С октября 1931 года Мюллер служит командиром роты 7-го сапёрного батальона в Мюнхене. Осенью 1932 года его переводят в штаб командующего 3-м военным округом в Берлин.
С приходом Гитлера к власти 30 января 1933 года начинается новая страница в карьере майора Винценца Мюллера. В апреле его переводят в штаб 7-го военного округа на должность руководителя развёртывания мобилизационных органов (Leiter des Aufbaus der Mobilmachungsorgane) . В 1935—1937 годах он служил в Генеральном штабе сухопутных войск на должности руководителя мобилизационной группы (Leiter der Gruppe Mobilmachung) . В 1937—1938 годах проходил обучение в Академии вермахта (Wehrmachtsakademie). После этого до самого начала войны Мюллер служил начальником оперативного отдела в штабе 2-й группы войск, размещённой в Касселе.
Начало Второй мировой войны полковник Мюллер встретил на должности начальника оперативного отдела в штабе группы армий «Ц», которая во время Польской кампании вермахта располагалась на германо-французской границе против линии Мажино. Во время проведения операции Гельб она располагалась на южном участке германского фронта и ей отводилась вспомогательная роль. Во время проведения германскими войсками заключительной фазы операции против французских армий она фронтальным ударом прорвала линию Мажино. 20 декабря 1940 года Мюллер получил новое назначение на пост начальника штаба вновь сформированной 17-й армии (занимал этот пост до 1 июня 1943 года). В её составе Мюллер участвовал в нападении на СССР и боях на территории Украины и Северного Кавказа. 1 февраля 1942 года он получил звание генерал-майора. В марте 1943 года, когда 17-я армия занимала плацдарм на Таманском полуострове, Мюллер был произведён в генерал-лейтенанты. Вскоре из-за тяжёлого нарушения кровообращения он был госпитализирован и вернулся на фронт только осенью. Недолгое время (1-19 сентября 1943 года)он командовал 57-й пехотной дивизией. С 15 ноября 1943 года по 10 июня 1944 года Мюллер командовал корпусной группой «Д», состоящей из остатков 56-й и 262-й пехотных дивизий. 7 апреля 1944 года он был представлен к Рыцарскому кресту Железного креста. 10 июня 1944 года сменил генерала Курта фон Типпельскирха на посту командира 12-го Армейского корпуса. 22 июня 1944 года советские войска начали крупномасштабное наступление в Белоруссии против группы армий «Центр» (Операция Багратион). Основные удары на первом этапе наносились против 3-й танковой и 9-й армий, находившихся соответственно севернее и южнее фронта 4-й армии, в составе которой находился корпус Мюллера. В ночь с 29 по 30 июня по приказу комндования Мюллер начал планомерное отступление в район южнее Минска. Курт фон Типпельскирх, командующий 4-й армией вместе со своим штабом эвакуировался в тыл уполномочив Мюллера отдавать необходимые приказания по армии в том случае, если связь будет прервана. Фактически с 30 июня и до 8 июля генерал-лейтенант Винценц Мюллер являлся командующим 4-й армией. 3 июля советскими войсками был взят Минск, восточнее которого в окружении оказались главные силы 4-й армии (около 100 000 человек). С каждым днём положение становилось всё тяжелее: практически полностью прекратилось снабжение, часть окружённых германских подразделений была раздроблена, штаб 12-го корпуса был рассеян. Процесс разложения усиливался по мере того, как советские войска во взаимодействии с партизанами, завершив общее окружение в районе юго-восточнее Минска, стали окружать отдельные части и соединения, попавшие в этот огромный котел. 5 июля 1944 года Мюллер направил в тыл последнюю радиограмму: «Сбросьте с самолета хотя бы карты местности, или вы уже списали нас?» Ответа не последовало.
Не имея с 4 июля 1944 года никакой связи с командованием и другими частями, Мюллер отдал 8 июля приказ солдатам 4-й армии прекратить сопротивление в районе Минска. Позднее он писал:
и
С самого начала своего пребывания в плену Мюллер начал активно участвовать в антифашистской деятельности. 3 августа 1944 года он стал членом Национального Комитета Свободная Германия и Союза Германских Офицеров. Часто выступал с комментариями в передачах радиостанции «Свободная Германия» и одновременно писал статьи в газете «Фрайес Дойчланд». В конце 1944 года он вместе с генералом Рудольфом Бамлером посещал специальные курсы антифашистов. 8 декабря 1944 года Мюллер подписался под воззванием НКСГ (так называемом обращении 50 генералов) в адрес германской группы армий «Север».
После своего освобождения из советского плена и возвращения в Германию в 1948 году Мюллер вступил в Национально-демократическую партию Германии. В 1949—1952 годах он был первым заместителем председателя этой партии и вице-президентом Народной палаты ГДР. В 1952 году он снова возвращается к военной деятельности и участвует в создании новой боеспособной армии ГДР. Винценц Мюллер был одним из немногих бывших генералов вермахта, которые получили это звание также и на службе в Национальной Народной Армии. С 1 сентября 1952 года по 29 февраля 1956 года он занимал должность начальника штаба и заместителя начальника Казарменной народной полиции. 1 октября 1952 года ему было присвоено звание генерал-лейтенанта. С 1 марта 1956 года, момента образования ННА, по 1 марта 1958 года Мюллер возглавлял Главный штаб Национальной Народной армии, одновременно являясь заместителем министра национальной обороны ГДР Вилли Штофа. Занимая руководящие посты в ГДР он тем не менее имел контакты со своими прежними товарищами, прежде всего из Баварии. В 1955 и 1956 годах он тайно встречался с тогдашним министром финансов ФРГ Фрицем Шеффером в Западном Берлине и вёл переговоры о возможности улучшения отношений между ФРГ и ГДР. Будучи бывшим офицером вермахта, Мюллер считался политически неблагонадёжным и в феврале 1958 года был отправлен в отставку. После этого он всё больше подпадал под давление Штази. В 1960 году Мюллер был объявлен страдающим шизофренией и некоторое время находился в госпитале. В это время появились данные о его причастности к массовым убийствам евреев в Артёмовске и расстрелам военнопленных. 12 мая 1961 года морально и физически истощённый Мюллер разбился насмерть, выбросившись с балкона собственного дома в пригороде Берлина. В 1963 году в свет вышла его незаконченная автобиография «Ich fand das wahre Vaterland»(Я нашёл подлинную родину. Записки немецкого генерала) под редакцией восточногерманского историка Клауса Маммаха.