לאחר מכן יצא לקורס קציני חי"ר אותו סיים בהצטיינות. שרת כמפקד מחלקה בצנחנים ולאחר מכן פיקד על פלוגת ב' בגדוד 202 בחטיבת הצנחנים במהלך הפעולות הראשונות מול ה"פת"ח" שהחל אז בבצוע פעולות חבלה במדינת ישראל. במסגרת זו נפצע קשה כאשר נטל חלק בפעולת סמוע – בדרום הר חברון - בנובמבר 1966. לאחר התאוששות מהפציעה שב לחטיבת הצנחנים, הוא לחם במלחמת ששת הימים בסיני וברמת הגולן. לאחר המלחמה מונה למפקד סיירת צנחנים. וילנאי פיקד על הסיירת במבצע תופת, שם נחת עם חייליו במסוקים בסמוך לעיירה כראמה שבירדן ולחם במחבלי הפת"ח. עם סיום תפקידו בסיירת שירת כסגן מפקד גדוד 202. באוקטובר 1968 נקרא על ידי מח"ט הצנחנים דני מט לחזור ולפקד על הסיירת במבצע אחד המבצע העמוק ביותר בשטח האויב עד לאותה עת - מבצע הלם 35 לפיצוץ תחנת שנאים במצרים עילית. לאחר מכן הועבר לחטיבת הבקעה לתפקיד קצין אג"ם חטיבתי, על מנת להחליף חבר שנהרג, רס"ן . בחטיבת הבקעה השתתף בעשרות מרדפים ופעולות מיוחדות.
בשנת 1970, לאחר שסיים בהצטיינות לימודים במכללה לפיקוד ולמטה של צה"ל מונה לסגן מפקד סיירת מטכ"ל. בסיומה של אותה שנה התמנה למפקד גדוד 890 – הגדוד שבו החל את שרותו הצבאי בחטיבת הצנחנים, ופיקד על שורה של פעולות מעבר לגבול, בתחומי לבנון ובהם מבצע "קנבוס 69" לפיצוץ בתי מחבלים בתנאי מזג אוויר קשים. ב-1972 מונה לקצין אג"ם בפיקוד המרכז, תחת פיקודו של האלוף רחבעם זאבי. בקרבות מלחמת יום הכיפורים עמד בראש כוח משימה מיוחד שפעל בחזית המצרית. ב-22 באוקטובר עמד הכוח בפיקודו, אשר כלל את סיירת חרוב וכוח של שייטת 13, לבצע פשיטה על פורט פואד אשר בוטלה בשל כניסת הפסקת האש הראשונה לתוקפה.
ב-1974 מונה למפקד חטיבה 55, חטיבת צנחנים במילואים וב-1975 מונה למפקד חטיבת הצנחנים הסדירה. השתתף במבצע אנטבה כסגן מפקד המבצע וכמפקד כוח הצנחנים. בשנים 1976–1978 פיקד על בית הספר לקצינים של צה"ל. ב-1977 מונה להקים את עוצבת חצי האש, חטיבת נ"ט חדשה יבילת אוויר וזאת כחלק מבניית תפיסה רחבה של הפעלת כוחות מוטסים בעומק שטח האויב. בשנת 1978 סיים את לימודיו במכללה לביטחון לאומי.
באוגוסט 1978, בגיל 34, מונה לתפקיד קצין חי"ר וצנחנים ראשי (קחצ"ר) והועלה לדרגת תת-אלוף. לאחר שלוש שנים שבהן עסק בעיקר בהטמעת לקחי מלחמת יום הכיפורים במערך החי"ר והצנחנים, מונה לתפקיד מפקד עוצבת געש, בסיום הקרבות בביירות, במלחמת שלום הגליל, פיקד על מבצע פינוי כוחות צה"ל מביירות.
בדצמבר 1985, לאחר חופשת לימודים כעמית מחקר במרכז ללימודים בינלאומיים באוניברסיטת הרווארד, הועלה לדרגת אלוף ושירת כראש אגף כוח האדם במטכ"ל ומשנת 1989 כמפקד פיקוד הדרום. בתפקיד זה שירת למעלה מחמש שנים בתקופת האינתיפאדה הראשונה. בתקופה זו פיקד על אזור הדרום ורצועת עזה והתמודד עם פעולות טרור קשות עד לחתימה על הסכמי אוסלו. בעקבות זאת יזם וילנאי את הקמת יחידת המסתערבים שמשון שפעלה ברצועת עזה. כן יזם וילנאי את הקמת יחידת לוט"ר אילת כדי להתמודד עם פיגועי מיקוח במרחב אילת והערבה. כמפקד פיקוד הדרום הוביל מדיניות של "מינימום חיכוך" בין כוחות צה"ל לאוכלוסייה המקומית. מדיניות שצימצמה בנפגעים אך גם הותירה חלל ריק. בתפקיד זה היה וילנאי אחראי לביצוע הפריסה מחדש ברצועת עזה, על פי הסכמי אוסלו, ולבניית גדר המערכת סביב רצועת עזה. ב-1994 מונה לראש אג"ם וסגן הרמטכ"ל, תחילה תחת אהוד ברק ולאחר מכן תחת אמנון ליפקין-שחק.
בנובמבר 1995, לאחר רצח ראש ממשלת ישראל יצחק רבין, הוביל את תכנון ההלוויה מתוקף תפקידו כסגן הרמטכ"ל.
בקיץ 1997 נפגש עם שר הביטחון יצחק מרדכי, אשר הציע לו לצאת לחופשת לימודים, ולאחר מכן להיכנס לתפקיד ראש המטה הכללי. בנובמבר 1997 סיים וילנאי את תפקידו כסגן הרמטכ"ל, ובינואר 1998 יצא לחופשת לימודים בארצות הברית והיה עמית מחקר במרכז ללימודים אסטרטגיים באוניברסיטת ג'ונס הופקינס בוושינגטון. וילנאי התמחה בנושא "המהפכה בארגון הצבאי לקראת שנת 2000" - ובארגון וניהול ארגונים גדולים.
במועד מינוי הרמטכ"ל הודיע מרדכי לממשלה כי בחר בשאול מופז לרמטכ"ל, בניגוד לצפוי. רבים, בהם וילנאי, טוענים שהסיבה לכך הייתה איבתו ארוכת השנים לווילנאי. בעקבות זאת פרש וילנאי מצה"ל ביולי 1998, בתום 36 שנות שירות, ופנה לפעילות ציבורית.
פעילות ציבורית ופוליטית.
את תפקידו האזרחי הראשון, עוד לפני הצטרפותו לפוליטיקה, הציע לו שר החינוך בממשלת הליכוד, הרב יצחק לוי, ומינה אותו לעמוד בראש הוועדה הציבורית למניעת אלימות בבתי הספר ('ועדת וילנאי' אשר הוקמה על ידי ד"ר יוסי בן-גל). מסקנות הוועדה אומצו על ידי שר החינוך יוסי שריד ומהוות מתווה מרכזי לטיפול באלימות בבתי הספר. בנוסף, עוד בטרם נכנס לפוליטיקה, היה וילנאי שותף בהקמתו של בית ספר לממשל במרכז הבינתחומי הרצליה.
עם שחרורו מהצבא, הוזמן על ידי יו"ר הליכוד, בנימין נתניהו, להצטרף לליכוד. הצעתו של נתניהו כללה את תפקיד שר הביטחון בממשלה שהתכוון להקים לאחר בחירות שנת 1999. וילנאי דחה את ההזמנה ובחר להצטרף למפלגת העבודה. אף על פי שהוגשו בפניו הצעות לשריון מקום ברשימת מפלגת העבודה לכנסת, בחר מתן וילנאי להתמודד בבחירות המקדימות של המפלגה. בתום קמפיין של שלושה שבועות בלבד, נבחר וילנאי למקום השלישי ברשימת מועמדי המפלגה לכנסת ה-15.
בממשלה ובכנסת.
עם הקמת הממשלה ה-28 בראשותו של אהוד ברק, בשנת 1999, מונה וילנאי לשר המדע, התרבות והספורט (המת"ס). בממשלה זו כיהן גם כיו"ר הוועדה לטקסים וסמלים וכיו"ר ועדת השרים לענייני האזרחים הערביים, בה עיצב תוכנית כוללת לטיפול בבעיות המגזר הערבי - "תוכנית 4 מיליארד השקל" והיה חבר בקבינט המדיני-ביטחוני. בתפקידו כשר הביא בין השאר לחקיקתו של חוק הקולנוע והקמת מועצה לאומית לתרבות, לחקיקת חוק הספורט המוטורי וחוק למניעת אלימות בספורט בדגש על מגרשי הכדורגל. בשנת 2001, לאחר הבחירות המיוחדות לראשות הממשלה, בהן ניצח אריאל שרון, אשר הקים ממשלת אחדות לאומית (הממשלה ה-29), המשיך וילנאי לכהן בתפקיד שר המדע התרבות והספורט וכחבר בקבינט המדיני-ביטחוני.
בשנת 2003, לקראת הבחירות לכנסת ה-16, נבחר וילנאי במקום הראשון בבחירות המקדימות של מפלגת ה"עבודה".
בשנת 2005 התמודד על ראשות מפלגת העבודה, אך כשבוע לפני הבחירות ויתר על התמודדותו ותמך במועמדותו של שמעון פרס מול עמיר פרץ ובנימין בן אליעזר. עם כניסת העבודה לקואליציה מונה וילנאי לתפקיד שר במשרד ראש הממשלה. וילנאי כיהן בתפקיד זה במשך שמונה חודשים, ולאחר מכן כשר המדע והטכנולוגיה כשלושה חודשים, עד פרישת מפלגת העבודה מהקואליציה. עם חזרתו לשורות האופוזיציה בכנסת, החל וילנאי לכהן כממלא מקום בוועדת החוץ והביטחון, עד הבחירות לכנסת ה-17 שהתקיימו מספר חודשים לאחר מכן.
בבחירות המקדימות של מפלגת העבודה לכנסת ה-17 נבחר וילנאי במקום השביעי. בכנסת ה-17 כיהן וילנאי כחבר בוועדת החוץ והביטחון, יו"ר ועדת משנה לנושאי כוח אדם וחבר בוועדת חוקה, חוק ומשפט.
במהלך כהונתו בכנסת יזם, בין היתר, את חוק זכויות הסטודנט (יחד עם אלכס מילר), וכן תיקון בחוק התשלומים לפדויי שבי, המרחיב את תחולתו גם לגבי פעילי מחתרות שנאסרו לפני 1947 (יחד עם חברי כנסת נוספים). בנוסף, כיו"ר ועדת משנה לנושאי כוח-אדם של ועדת החוץ והביטחון החל וילנאי בקידום חוק המילואים אשר היה מונח שנים על שולחן הוועדה.
ב-2 ביולי 2007, עם מינויו של אהוד ברק לתפקיד שר הביטחון מונה לתפקיד סגן שר הביטחון בממשלה ה-31. במסגרת תפקידו הוטלה על וילנאי, בין השאר, אחריות על מערך המילואים ומערך העורף של מדינת ישראל, בעקבות לקחי מלחמת לבנון השנייה. בתקופת כהונתו העביר וילנאי את חוק המילואים וכן הקים את רח"ל - רשות חירום לאומית.
בבחירות המקדימות של מפלגת העבודה לכנסת ה-18 נבחר וילנאי במקום החמישי. עם כניסת מפלגת העבודה לקואליציה הוצע לו תפקיד שר בממשלה, אך וילנאי העדיף להמשיך בתפקיד סגן שר הביטחון גם בממשלה ה-32.
ב-17 בינואר 2011 פרש ממפלגת העבודה יחד עם ארבעה חברי כנסת נוספים בראשותו של שר הביטחון, אהוד ברק, והקים אתם את סיעת העצמאות. בעקבות המהלך מונה וילנאי לשר להגנת העורף.
בפברואר 2012 הוחלט למנותו כשגריר ישראל בסין וב-13 בחודש הגיש את התפטרותו מהכנסת ונשאר לשמש כשר בממשלה עד היכנסו לתפקיד השגריר. ב-15 באוגוסט 2012 התפטר וילנאי מהממשלה.
בזמן כהונתו כשגריר, יצא וילנאי בביקורת קשה כלפי פקידי משרד האוצר על התנהלותם כלפי משרד החוץ ופגיעתם בתנאי השירות של שליחי המדינה בחו"ל, שאותה כינה "בריונות ושרלטנות".
ב-2020 מונה ליו"ר הארגון "מפקדים למען ביטחון ישראל".
קשריו עם סין.
בפברואר 2012 החל מתן וילנאי לשמש כשגריר ישראל בסין. במסגרת כהונתו הועמקו היחסים בין המדינות והורחבה הפעילות הישראלית בסין.
וילנאי יצר וטיפח קשרים רבים עם הנהגת המדינה והמגזר העסקי בסין, מה שהוביל להגדלה משמעותית של היקף השקעות ההון מסין בישראל ולפיתוח תוכנית פעולה כוללת לקידום והרחבת הקשרים הכלכליים בין שתי המדינות.
במסגרת הידוק הקשרים, וילנאי היה מעורב בהקמת נציגות משרד האוצר בבייג'ינג, בכתיבת פרוטוקול סחר מלא בין המדינות ולכניסת ישראל כחברה שותפה-מייסדת בבנק ההשקעות האסייתי לפיתוח תשתיות לאומיות.
בנוסף, יזם תוכנית להקמת רפתות מתקדמות בטכנולוגיה ישראלית במחוז חיילונג-ג'יאנג, הטמעת טכנולוגיות מים ישראליות בערים סיניות והקמת נציגות דיפלומטית חדשה בעיר צ'נגדו.