מרדכי זעירא נולד ב-6 ביולי 1905 בקייב אשר באוקראינה, בן בכור לאביו גרישה (צבי) גְרְיֶבִּין ואמו אספירה (אסתר). אחריו נולדו עוד אחות ושני אחים. פירוש השם Gr-ye-bin ברוסית הוא 'מסרק'. שמו הרשמי היה מארק ושם החיבה שלו היה - מיטייה. שנת לידתו הייתה שנת פרעות ביהודי רוסיה, ויושבי עליית הגג בה הסתתרה המשפחה הצעירה, כך סופר לו, רצו לחנוק אותו בהיותו תינוק, מחשש שבכיו עלול למשוך את תשומת לב הפורעים. אביו החליף עיסוקים, תחילה עסק בסחר עצים שקנה מיערן מקומי, אחר כך פתח מאפיה, ולאחר מכן - מסעדה גדולה שקיימה את משפחתו בכבוד, עד שהולאמה בזמן המהפכה. את בית הוריו זכר זעירא כבית יהודי חם, ציוני ומתבולל כאחד, בו דיברו הרבה על המולדת הרחוקה והעתיקה.
הוריו היו אוהבי זמר, אך לא העניקו לו חינוך מוסיקאלי. הוא סיפר שאביו נהג להרדים אותו בעזרת שיר, ואמו שרה שירים ביידיש ושירים ציוניים ברוסית, בחברת אורחי ביתם, או כשעסקה בעבודות הבית. בן חמש כבר נכח עם אמו בהצגת האופרה 'בוריס גודונוב', לאחר שקיבל ממנה הסבר מוקדם על הסיפור. באוטוביוגרפיה שהחל לכתוב (אך נטש אחרי הדפים הראשונים), העיד שאותה אופרה עשתה עליו רושם כביר ונטעה בו את ההרגל לבקר בכל אירוע מוסיקאלי ותיאטרוני שהיו בהישג ידו.
באותו גיל כבר שכר אביו למענו מורה שילמד אותו עברית. את העברית, שלמד אז, שכח עם השנים, אבל מאוחר יותר, כשעלה לארץ ישראל, עזרו לימודיו אלה להיזכר בה. שנתיים לפני שהגיע למצוות לקח אותו אביו יום יום לבית הכנסת, למענו, כדי שיספוג עוד יותר מן המסורת. כשהוטב מצבה הכלכלי של המשפחה, קיבלה אחותו לוסיה שיעורי פסנתר, ואת החינוך המוסיקאלי הראשוני הוא קיבל כשהאזין בשקט לשיעורי הפסנתר שלה. לימודים אלה פסקו די מהר, כשאחותו החליטה "לשבות" מהם.
זעירא סיים את לימודיו בבית הספר התיכון, והחל בלימודי מכונאות בפוליטכניקום בעיר הולדתו, אך כעבור שני סימסטרים נטש את לימודיו. הוא הצטרף לתנועת הצופים הכללית בקייב ובד בבד הצטרף לחברים יהודים אחרים, שהתכנסו בחשאי בבתים פרטיים כתנועת 'צופיות עברית', שנקראה בשם 'השומר הצעיר' (ללא קשר לתנועת 'השומר הצעיר' הידועה בישראל). לקבוצת הבוגרים שבנערים, שהיו מועמדים לעלות לישראל, ניתן השם 'השומרים'. כיון שפעילות ציונית זו הייתה אסורה ברוסיה, עצרו השלטונות אותו ואת חבריו, ולאחר חקירה הוא נכלא כ'אסיר ציון'.
בבית הסוהר פגש יהודים רבים, שראה בילדותו בבית הוריו, מבלי לדעת שגם הם היו קשורים לפעילות ציונית כלשהי. החוקר מטעם השלטונות, יהודי דובר עברית ויידיש, הציע לו לרגל נגד חבריו, ובתמורה הבטיח לו מילגת לימודים בקונסרבטוריון למוסיקה בקייב. למרות שדחה את ההצעה, לא נשלח לסיביריה, אבל גורש מרוסיה. בדרכון שקיבל (מהנציגות הבריטית) הוטבעה חותמת שאסרה עליו את הכניסה לרוסיה למשך עשר שנים, והוא הורשה לצאת לדרכו אל פלשתינה, אליה הגיע ב-1924 והוא בן שמונה עשרה וחצי שנים.