המפרשית הדה
בניית מפרשית החילוץ

למרות אובדן ספינתו המשיך פוטיאטין במשא ומתן המדיני, ואף הצליח לקשור קשרי ידידות קרובים עם ראש המשלחת היפנית קוואג'י טושיאקירה. בעקבות טביעת הדיאנה ביקש פוטיאטין אישור ממארחיו לבנות על אדמת יפן ספינה חלופית, על מנת לאפשר לו ולצוותו לשוב לרוסיה. כשהועלה הנושא בממשל היפני הביעו גורמים רבים התנגדות לכך, ואף היה מי שחשב שיש להוציא להורג את כל אנשי המשלחת הרוסית. אך ראש צוות המשא-ומתן היפני, טושיאקירה, חשב אחרת והחליט בעצמו לאשר לפוטיאטין את מיזם בניית הספינה. הוא נימק זאת בפני הממונים עליו בכך שהספינה שתיבנה לא תהיה ספינת מלחמה אלא כלי שיט אזרחי לחילוץ הצוות הרוסי. חשוב היה לדעתו לסייע לספנים שנקלעו לאסון טבע, מה עוד שהרוסים נחלצו להצלת דייגים יפנים בזמן האסון. הוא סבר שיש לנצל את המצב אליו נקלעו הרוסים לטובת הצד היפני. אישור בניית ספינת החילוץ עשוי להיחשב כמחווה יפנית שתשפר את עמדת יפן במשא ומתן הנמשך. בנוסף לכך, טושיאקירה היה ער לטכנולוגיה הנחותה של המספנות היפניות באותה עת, והבין שתהיה זו הזדמנות טובה ללמוד מקרוב מהרוסים פרטים אודות תכנון ושיטות בנייה של ספינות מערביות.
בעוד רוסיה נמצאת במלחמה עם צרפת ואנגליה (מלחמת קרים), ומחשש להתקפה על אנשיו, ביקש פוטיאטין לבנות את ספינת החילוץ באתר מוסתר היטב, ובחר לשם כך בכפר "הדה" בצד המערבי של חצי האי איזו. המפרץ הצר של הדה, המוקף הרים משלושה עברים, סיפק מחסה מצוין מעיני הספינות של אנגליה וצרפת ששייטו בקביעות סמוך לחופי יפן. פוטיאטין ומאות אנשיו הגיעו להדה בדרך היבשה והתמקמו בכפר הקטן שמנה כ-3000 תושבים בלבד. הצוות הרוסי השתכן בבתי משפחות בכפר ופוטיאטין קבע את מושבו באחד המקדשים במקום. הוא בחר שטח מצומצם, של כ-900 מטר מרובע בלבד, סמוך למי המפרץ, שהוכשר לשמש כמזח לבניית הספינה. לצורך תכנון הספינה נעשה שימוש במסמכים ושרטוטים שחולצו מהדיאנה, טרם טביעתה, על ידי קצין ההנדסה של המשלחת הרוסית - אלכסנדר מוז'ייבסקי. בתוך מספר שבועות תוכננה מפרשית דו-תרנית חדשה באורך 25 מטרים, ברוחב 7 מטרים ובמשקל של 80 טונות המתאימה לשאת כ-50 איש. שני התרנים היו בגובה 21 מטרים ועל הסיפון לא היו תותחים. היא עוצבה כדי לאפשר שייט מהיר הודות לחרטום מחודד ומבנה גוף צר. גודלה הצנוע איפשר בנייה מהירה יחסית על מנת להקדים ככל הניתן את ההפלגה חזרה לרוסיה. השרטוטים הראשונים כללו טקסטים ברוסית והיה בהם שימוש במידות מערביות. בעזרת צוות מקומי תורגמו ההוראות להולנדית, ומהולנדית ליפנית. שר הימייה היפני גייס למשימה את מיטב נגרי הספינות, ובראשם אואדה טוראקיצ'י (Ueda Torakichi), שהועבר להדה מטוקיו. לרשות צוות הנגרים עמדו כשלוש מאות חרשי עץ מנוסים. מרגע שהתוכניות היו מוכנות, הבטיחה מיומנותם של הנגרים היפנים התקדמות מהירה. הם השתמשו במסורים דקים כדי לעצב בדייקנות את ההתאמה בין לוחות העץ של גוף הספינה ובכך השיגו הידוק ואטימה מרבית. זאת בשונה משיטת הבניה המערבית, בה נאטם מבנה הספינה באמצעות חומרי אטימה שנמרחו במרווחים בין לוחות העץ. ספינת החילוץ נבנתה על פי תכנון רוסי ובשיטות עבודה יפניות.
במקביל לעבודה על ספינת החילוץ, המשיך פוטיאטין לנהל את המשא ומתן המדיני מול הצוות היפני בשימודה. בתחילת פברואר 1855 הגיעו הצדדים להסכמות וב-7 לחודש נחתם הסכם "שימודה" במקדש צ'ורקוג'י (Chorakuji) בעיר. בהסכם מכריזות שתי המדינות על כינון שלום ביניהן, יחסי ידידות בין שני העמים, והוא מפרט שורה של הבנות בנושאים פוליטיים, כלכליים, מסחריים וקונסולריים. ההסכם כלל הסכמה יפנית לפתיחת מספר נמלים בפני ספינות רוסיות לצורכי אספקה ותחזוקה, וכן להצבת קונסוליות רוסיות בנמלים אלה.
גם בניית ספינת החילוץ התקדמה בקצב מהיר וכעבור כשלושה חודשי עבודה, במרץ 1855, גוף הספינה היה מוכן לטבילה בים. בהתאם לשיטות הנהוגות במספנות מערביות, נבנתה הספינה כשהיא נחה על מסילה מקורות עץ שנבנתה על יסודות מאבן בשיפוע לכיוון המים. בתום הבנייה שימשה המסילה לשיגור הספינה אל המים. מבנה מסילת ההשקה היה בבחינת חידוש גדול ליפנים והם למדו אותו מקרוב. בשיטה היפנית הספינות נבנו על החול בחוף הים, ונגררו במאמצים רבים אל המים, תהליך שגזל זמן רב ולעיתים נמשך מספר ימים. כשהייתה הספינה החדשה מוכנה על מתקן ההשקה, שומנו היטב קורות המסילה ובהינתן האות היא החליקה במהירות, תוך דקות, אל המים. ציור יפני רשמי מתאר אירוע ייחודי זה, שבסופו, כאשר הספינה צפה במי המפרץ מיהרו רבים מהצופים לברך את פוטיאטין.
פוטיאטין קרא לספינה "הדה" כהוקרה על התמיכה והעזרה שקיבלו הרוסים מאנשי הכפר. ב-8 במאי 1855 הפליגה ה"הדה" לרוסיה.