בעדותו השמורה בארכיון מורשת, הוא מספר על ההתרחשויות במחנה ערב היציאה לצעדה:

"ערב אחד, ב-17 בינואר 1945, שמתי לב לתכונה מיוחדת בתוך הבלוק. אנשים מתרוצצים, כל אחד מכין לו איזה תרמיל ואורז את החפצים האישיים. לא הבנתי מה קורה... לא ידענו מה פשר הדבר, בכל אופן, נדלקו אצלנו נורות אזהרה. הייתה לנו מן רגישות מיוחדת להתרחשויות לא-שגרתיות. זה היה כבר בדם. כששכבתי באותו ערב לישון, לא תיארתי לעצמי שיהיה זה הלילה האחרון שלי באושוויץ", בבוקר המחרת, ה-18 בינואר, "איש הס"ס האחראי הודיע לנו פתאום שמפנים אותנו וכולנו יוצאים מיד לדרך. פרצה בהלה, התרגשות... מה שהדאיג במיוחד היה שלא קיבלנו אפילו את מנת המרק ויצאנו בלי כל אוכל לדרך. צעדנו בליווי אנשי ס"ס עד לבירקנאו במצב-רוח קודר במיוחד. בדרך ראיתי שיירות בנות רבבות אסירים ואסירות עם שקיות ותרמילים.במגרש המסדרים לשם הביאו אותנו, שררה אנדרלמוסיה בלתי רגילה. במהומה שנוצרה איבדתי את החברים שלי, כשהתאוששתי מצאתי את עצמי לבד, מוקף בקבוצה של אסירים מוקפים אנשי ס"ס... אני יכול לסכם, שדווקא היום האחרון שלי באושוויץ היה אחד הימים המדכאים ביותר עבורי. הרגשת הבדידות בשעה גורלית זו, השפיעה בצורה חמורה על מצב הרוח.הייתי מיואש, לא חשתי מה מתחולל סביבי".

על צעדת המוות עצמה, מספר יהושע: "הצעדה התנהלה בקצב מהיר ביותר ומי שלא צעד בשורה או שפיגר קיבל כדור בראש.ראיתי אנשים רבים שנרצחו, שוכבים בצדי הדרך... איכרים פולנים וגרמנים הביטו עלינו מהחצרות, על המדרכות עמדו קבוצות של נוער-היטלר וירקו עלינו. על קירות הבתים הודבקו סיסמאות שקראו להתגוננות מפני הסכנה הבולשביקית. על הגגות התנוססו דגלים נאציים... בלילה הגענו לאיזה כפר, הכניסו אותנו לדיר באחת החוות. נפלתי באפיסת כוחות על הרצפה ונרדמתי. התעוררתי לשמע יריות, כנראה כמה אסירים ניסו לברוח. בבוקר גירשו אותנו לכביש והמשכנו בצעדה. אוכל לא קיבלנו בכלל. זה היה המצעד הידוע לשמצה כמצעד המוות".