經過近一年的精心準備，由鎮海指揮使王德用親自統領的鎮海水師再次出航。
此次船隊規模遠非前次探索可比：大小艦船十五艘，以新下水的三艘載重三百料、兼具風帆與划槳的探索型戰船定波、靖海、伏戎號為核心。
輔以多艘經過加固改造的運輸船、補給船，載有水師官兵八百餘人，工匠、通譯、醫師、繪圖師等各類專業人才近百名。
並攜帶了大量用於貿易、饋贈的絲綢、瓷器、茶葉、漆器、鐵器等貨物，以及楊再興以康居都督、安西大都護名義，寫給黑海沿岸諸國、諸城邦、諸部首領的國書副本。
船隊的任務明確而艱鉅： 循著去歲張順探明的航線，經裡海、亞速海，穿越刻赤海峽，正式進入黑海，探明航道，繪製詳圖，並與沿岸勢力進行官方接觸，重點是拜占庭帝國在黑海的重要港口特拉布宗，以及熱那亞人在克里米亞南岸的殖民據點卡法。
同時，尋找一處合適的地點，建立一個小小的、永久性的補給與情報前哨站，為日後可能的軍事、貿易、外交活動提供支點。
“此行非為征伐，而在探路、通好、立點。”
出航前，楊再興在鎮海城碼頭，對王德用及主要將領再三叮囑，“黑海之濱，邦國林立，形勢複雜。拂菻國雖與大食時有齟齬，然其文明久遠，兵甲尚強，尤擅舟師，不可輕侮。
熱那亞、威尼斯等意大里亞城邦，精於商賈，艦船犀利，其心唯利，當以貿易結之，以威示之。
至於沿岸諸部，或勇悍難馴，或搖擺不定，宜恩威並施，使其知我大宋之富庶強盛，懷德而畏威。
選址立點，務求地勢險要，有淡水，可泊船，且不與他國緊要之地衝突，寧僻遠而穩固，勿繁華而多事。”
“末將謹記都督教誨！” 王德用抱拳領命，神色肅然。
他知道，此行不僅是軍事探索，更肩負著為大宋在黑海這個完全陌生的戰略水域，落下第一枚棋子的重任。
船隊揚帆起航，沿著日益熟悉的東西岸航線向北，再折入亞速海。
有了去年的經驗和更詳細的海圖，此次航行順利許多。
在亞速海，他們再次遇到了塔曼領主的巡邏船隻。
王德用沒有迴避，而是主動表明身份，出示楊再興的文書，並饋贈了比上次更為豐厚的禮物。
塔曼領主對這支規模龐大、裝備精良的陌生船隊既驚且疑，但在重禮和宋軍船隊顯露出的嚴整軍容面前，選擇了友好態度，不僅提供了刻赤海峽最新的水文資訊，還派出一名熟悉海峽航道的嚮導隨行。
穿過狹窄而風急浪高的刻赤海峽，眼前豁然開朗。
浩瀚、深邃、呈現出獨特暗藍色的黑海，以其無垠的胸懷，迎接著來自遙遠東方的訪客。
不同於裡海的封閉與亞速海的淺平，黑海波濤更為壯闊，海天一色，令人心生敬畏。
船隊沿著海岸線，小心翼翼地向南偏西航行，首先抵達了克里米亞半島的東南端。
在這裡，他們第一次親眼目睹了熱那亞人在海角險要處建立的殖民據點——卡法。
石砌的城牆、高聳的塔樓、港口內停泊的有著典型地中海風格槳帆船、以及飄揚的熱那亞旗幟，無不顯示著這座城市的繁榮與堅固。
卡法的熱那亞人對突然出現的、前所未見的東方大型船隊極為震驚，港口一度戒備。王德用下令船隊在港外下錨，派出通譯乘小船攜禮物和國書副本入港交涉。
熱那亞商人總督在驚訝之餘，出於對未知東方強權的謹慎和貿易利益的巨大誘惑，最終允許宋軍船隊派出少數代表入港，並在指定區域進行有限的貿易。
在卡法，宋人首次與義大利城邦的商人、水手、官員進行了首接接觸。
