נולד בוורשה, פולין. היה חבר תנועת השומר הצעיר ובמהלך פעילותו בתנועה הכיר את יצחק אדל שהקים מקהלת צעירים ששרה שירים עבריים וניצח עליה. יצחק אדל כיוון אותו ללימודים בקונסרבטוריון הממלכתי בוורשה שם למד תיאוריה, קומפוזיציה וניצוח, והשפיע רבות על דרכו המוזיקלית.
וילנסקי עלה לארץ ב- 1932 כשהוא בוגר הקונסרבטוריון בוורשה, ומרגע עלותו לארץ עסק אך ורק במוסיקה. הוא חיבר מוסיקה, ליווה זמרים גם כששרו יצירות שאינן שלו, עסק הרבה מאד בעיבוד יצירות לתזמורת, יצירות שלו וגם יצירות של אחרים. כמו-כן עסק הרבה מאד בהקלטות. שירם של עמנואל הרוסי ומשה וילנסקי 'דודה הגידי לנו כן' מתוך הצגת המטאטא 1933 היה התקליט הראשון של זמר עברי שנוצר בארץ. יצקו אותו בפרדס במזרח תל-אביב על-ידי חברה שנקראה 'אחווה'. זה היה אחד מאותם תקליטי קרטון מצופים בקליט שהיו טובים רק לשימוש זמני שכן לפעמים המחט היתה נוקבת חור בתקליט ויוצאת מעברו השני.
מאז עלייתו לארץ עסק וילנסקי במוסיקה בלבד (בניגוד למלחינים אחרים כמו סשה ארגוב או מרדכי זעירא שעבדו לפרנסתם במקצוע שאינו קשור למוסיקה). וילנסקי אף פעם לא התמקד אך ורק במוסיקה שלו. הוא ניצח על תזמורות, עיבד וניצח על ביצועים ללחנים שאינם שלו. הוא עבד ב'מטאטא' כפסנתרן וכמלחין, היה המנהל המוסיקלי של תיאטרון 'לי לה לו', הגיש תכניות רדיו, ניהל את מחלקת המוסיקה הקלה של קול-ישראל, והיה המנצח של תזמורת הבידור. וילנסקי היה במידה רבה גם איש הבמה הקלה: אהב ג'אז, אהב את המוסיקה האירופית, הוא גם ניגן אותה בבתי-קפה ובבתי-מלון. בשנות הארבעים, ניגן לפרנסתו בקפה 'ארמון' בתל-אביב אשר ב'מלון הירקון'. אחר-כך עבר לנגן בחיפה במועדון לילה בשם 'פיקדילי' וחזר לתל-אביב לנגן בקפה 'נגה'. הוא היה איש המוסיקה הקלה והיתה לכך השפעה על כתיבתו ועל יחסיו עם המלחינים שהיו אז מקובלים כמעצבי סגנון ארץ-ישראלי כמו עמירן, זהבי ואחרים. על כך וילנסקי לד"ר טלילה אלירם בראיון עמו:
'אני סבלתי מסיבה זו כי אף פעם הם לא קיבלו אותי לקהילה של הקומפוזיטורים הישראליים כי אני הייתי זר.. אני הייתי כאילו מוחרם, כי המוסיקה שאני כתבתי הייתה זרה להם והם כתבו מוסיקה ישראלית - אני כתבתי מוסיקה זרה.. אני כתבתי בסגנון בינלאומי, את המוסיקה הקלה, ואני מאד אהבתי ג'אז אז כתבתי משהו שהיה קרוב לג'אז. אני אהבתי את ההרמוניות של ג'אז, אני אהבתי את ההרמוניה האירופית המקובלת'.
בעניין זה כתב עליו אהוד מנור כאשר ספד לו (ידיעות אחרונות, 3.1.97): 'הגדולה של משה הייתה בפתיחות שלו לעולם הגדול. הוא ידע להלחין גם שירים קלים באוריינטציה ג'אזית אמריקאית, מה שנקרא שירים סלוניים. בשבילו הבידור הקל היה אמנות בפני עצמה. לא היה לו תסביך של יומרה, הוא חש בעצמותיו שככל שהמוסיקה עממית ומחוברת לחיי היומיום, כך היא יותר גדולה'.
בנוסף לעבודתו בבתי הקפה הוא עבד גם בתיאטראות הבידוריים. הוא החל את עבודתו בתאטרון 'המטאטא' שם הכיר את הזמרת אסתר גמליאלית וכתב לה מספר שירים בסגנון תימני, עבר לתאטרון 'כל הרוחות' שם כתב את שירו 'צריך לצלצל פעמיים' (מלים של אלתרמן). בשנת 1944 עבר ל'לי לה לו', שם נוצר שיתוף הפעולה בין אלתרמן, וילנסקי ושושנה דמארי והשיר הראשון של השלישיה הזו היה 'כלניות'. מאז נוצר הקשר הזה הוא נמשך שנים רבות והניב שירים רבים. בתקופת מלחמת השחרור עברו וילנסקי ודמארי בין החיילים והופיעו בפניהם. ב-1949 הם נסעו לארה"ב והופיעו שם. הכתיבה לבמה נגמרה כמעט לחלוטין אצל וילנסקי עם התפרקותו של תאטרון 'לי לה לו'. הוא כתב עוד יחד עם מוהר את השירים לאופרטה 'שולמית' (למשל השיר 'אנחנו הרועים'), הסיפור על-פי גולדפאדן (האופרטה הוצגה בשנת 1957). הוא הלחין מוזיקה לחברת יומני כרמל, ומוזיקה לסרטים - לסרט 'עמוד האש' ('היה הוא אפור'), לסרט 'באין מולדת' ולסרט 'דן וסעדיה הולכים העירה' (שני הסרטים הוקרנו לראשונה ב-1956). מאוחר יותר כתב בעיקר לזמרים בודדים וללהקות הצבאיות וגם ללהקת 'בצל ירוק' ('ונצואלה', 'שברו את הכלים'). הוא גם הלחין בשנת 1965 את שירי המופע 'שוק המציאות' שהיה מופע משירי נתן אלתרמן ובו השתתפו יונה עטרי ואילי גורליצקי. בין השירים שהושרו במופע זה: 'אלימלך', 'בכל זאת יש בה משהו', 'קונצרטינה וגיטרה', 'לימון וצלחת' ועוד.
במקביל לכתיבה הקלה הלחין וילנסקי ללהקות הצבאיות: ללהקת הצ'יזבטרון הלחין (יחד עם חיים חפר) את השירים 'הקרב האחרון', 'היו זמנים', 'הצ'יזבאט'. בשנות החמישים החל בעבודה משותפת עם יחיאל מוהר. תחילה כתבו רפרטואר שירים ללהקת הנח"ל, ואחר כך כתבו גם לזמרים אחרים. השיר הראשון שכתבו יחד היה 'הורה ממטרה' (1954) ובעקבותיה נכתבו שירי 'תקופת המסתננים' (כפי שאליהו הכהן מכנה אותם). בשנת 1955 נכתבו: 'שיר ערש נגבי', 'כיתה אלמונית', 'הורה נתגבר', 'רק לא סייר' ו-'פלטיאל'. בשנים 1956-1957 כתבו וילנסקי ומוהר, בין השאר, את השירים: 'יא משלטי', 'בלדה על מעיין וים', 'רחל רחל', 'לצועדים הידד', 'כרמלית', 'כשמתחילים ללכת', 'מול הר סיני' ו-'צ'יזבטים'. יש לציין שחלק מן השירים שחוברו עבור ללהקת הנח"ל קיבלו את פרסומם לאחר ששושנה דמארי הקליטה אותם, כמו למשל 'שיר ערש נגבי', 'כיתה אלמונית' ואחרים. אחד השירים המרגשים שכתב הצמד ללהקת הנח"ל הנו תיעוד של ביקור משלחת נוער במוסקבה בשנת 1957, אותה מוסקבה אנטישמית שהצרה את רגלי היהודים. ביקורם של החיילים שם, כך התברר, נתן ליהודים הזדמנות להביע את הזדהותם עם העם היהודי. בהמשך הלחין וילנסקי שירים רבים ללהקות צבאיות אחרות, להלן כמה דוגמאות: 'המלח שלי הוא המלאך שלי' (מלים: יורם טהר-לב) ללהקת חיל הים; 'שריונים 69' (מילים: יורם טהר-לב) ללהקת חיל השריון; 'חסקה' (מילים: יורם טהר-לב) ללהקת חיל הים; ו'אילת' (מילים: דליה רביקוביץ) ללהקת פיקוד דרום.
שירים רבים הלחין וילנסקי לזמרות תימניות כמו מרים גמליאלית, חנה אהרוני, ושושנה דמארי. הוא אף הלחין הרבה שירים ב'גוון' תימני כמו: ב'כרמי תימן' (מילים: נתן אלתרמן), 'מרבד הקסמים' (מילים: יחיאל מוהר), 'זכריה בן עזרא' (מילים: יחיאל מוהר), 'מרים בת נסים' (מילים: נתן אלתרמן), ו-'זוהרה' (מילים: רפאל קלצ'קין). וילנסקי אהב את המוסיקה התימנית המקורית. בראיון עמו (שערכו פרופ' אדוין סרוסי וד"ר טלילה אלירם) ציין שקראו לו 'התימני מוורשה' ומצאו 'תימניות' במנגינות שכתב. וילנסקי ציין כי בתקופת החגים היה נוהג לבוא לבית הכנסת בכרם התימנים שם היה סופג את המוסיקה התימנית.
בראשית שנות החמישים הגיש וילנסקי סדרת תכניות רדיו בשם 'פזמון וזמר' בקול-ישראל. הסדרה הייתה ערוכה לפי נושאים כאשר לכל נושא ייעד והלחין שיר חדש: לשירי מלחמה כתב את 'משלט עזוב'; לשירי רועים את 'הרועה הקטנה מן הגיא'; לשירי אהבה את 'דודי ירד לגנו'; ולשירי זכרונות 'לאור הזכרונות'. החל משנת 1961 שימש במשך שנים רבות כמנהל מחלקת המוזיקה הקלה בקול ישראל.
פן נוסף ומוכר פחות בעיסוקיו של וילנסקי אך תוצריו מוכרים לכולם הוא הכתיבה לפרסומות. דוגמה טובה לכך היא המנגינה הפרסומת הידועה לסבון 'נקה 7' ('הוא כחול, הוא ורוד, הוא לבן..').
וילנסקי השתתף במספר פסטיבלים ביניהם פסטיבלי ילדים. בפסטיבל מס' 3 לשירי ילדים ב- 1972 זכה שירו 'אבראקדברא' (מילים: לאה לופנפלד) בפרס שני. וילנסקי היה למלחין הישראלי הראשון ששיריו זכו להכרה בין לאומית בתחרויות מוסיקה, כאשר השיר 'סתיו' (לחן: משה וילנסקי מילים: שמשון חלפי) זכה בשנת 1963 בפרס שני בפסטיבל 'צופוט' בפולין. שנה לאחר מכן זכה שוב שירו 'לילה ועשן' (מילים: יחיאל מוהר) בפרס שני. אחד משיריו היפים של וילנסקי, 'דצמבר', נכתב עבור פסטיבל שירי משוררים שנערך ע'י גלי צה'ל בשנת 1972. 'דצמבר' נכתב ע'י אלתרמן בשנות השלושים, אך הולחן ידי וילנסקי כארבעים שנה לאחר מכן בשנות השבעים על שיר זה אמר אהוד מנור: 'יש בשיר את כל העצב והאופטימיות והתמימות שאפיינו את וילנסקי כאדם'.
וילנסקי הלחין מספר רב של שירי ילדים להם הוקדש מדור שלם בספרו 'על הכביש ירח' (1982). 'שעון בן חיל' ו-'דובי דובי שן' הן דוגמאות לשירים שהפכו לנכסי צאן ברזל בתרבות הילדים הישראלית מאז ועד היום.
וילנסקי זכה בשנת 1983 בפרס ישראל בתחום הזמר העברי.
שירו האחרון נכתב יחד עם אהוד מנור עבור שושנה דמארי ושמו 'כשאני עומדת על במה' (1997). השיר הושר לראשונה בפסטיבל ערד של אותה שנה.
על וילנסקי כתב המבקר חנוך רון: 'שיר אמיתי הוא ראי של חברה, של עם, של היסטוריה. והשיר של וילנסקי היה ועדיין הראי של כולנו. הוא שיקף אותנו בכל תקופת המאבק שלפני המדינה, ורץ איתנו בהמשך לאורך כל הדרך: מסביב למדורה, בצבא, בעיר, במסיבות, בבידור, על הבמה. השיר של וילנסקי הוא אכן שיר אמיתי, כי הוא 'יושב' לנו תמיד באופן טבעי בפה.. לשיר של וילנסקי יש טעם מיוחד: צירוף של שנסון צרפתי, פלוס שיר תימני, כשהכל מהול בתוך פזמון תיאטרלי. וילנסקי כמו הפשיט מהזמר הישראלי את החליפה הרוסית והייקית שלו'.
שיריו הופיעו במספר ספרים: 'תמיד כלניות תפרחנה', 'על הכביש ירח', ו'זר כלניות'.
וילנסקי ייסד את איגוד הקומפוזיטורים אקו"ם בשנת 1936.
