查士丁尼統治第七年，大約在夏至（公元533年6月），整個艦隊600艘船在皇宮花園前的海面，排列出軍威雄壯的校閱陣容。教長向全軍將士祝福，皇帝下達最後的命令，將領的號角手發出開拔的信號，每個人根據畏懼或期望的情緒，帶著焦慮而好奇的心理，搜尋那些可能帶來失敗或成功的徵兆。貝利薩留先在佩林里烏斯或赫拉克利亞停留5天，接受國君送來的幾匹色雷斯駿馬，作為旗開得勝的禮物。從這裡開始順著航道穿過普洛蓬提斯海，當他們在赫勒斯滂海峽掙扎前進時，遭到一陣妨礙航行的頂頭風，迫得要在阿比杜斯等待4天。這時將領顯示出堅定而又嚴苛的軍紀要求，令人終生難忘。3個匈奴人在酒醉以後發生爭吵，其中一個被同伴殺死，將領立即下令將兇手弔死，懸屍示眾。他們的族人認為這種做法侮辱了他們的民族尊嚴，拒絕接受帝國把人視為奴隸的法律，要求維護西徐亞人自由的特權，對於酒醉和氣憤的突發行為，只能用少量罰鍰作為補償。他們的抱怨很像回事，發出大聲的叫囂，羅馬人對於這種不守秩序的行為，沒有追究視若等閑，但很快就顯露出嘩變的危險，將領出面靠著權威的地位和出色的辯才，才將他們安撫下來。他對集合的部隊講話，提到他要善盡公正的責任，強調紀律的重要，行為良好和信仰虔誠的人會獲得獎賞，謀殺是不可饒恕的罪行，在酗酒惡習 助長之下，寬恕會產生更為嚴重的結果，這才是令人感到極為憂慮的地方。
從赫勒斯滂海峽到伯羅奔尼撒的海上航行，當年希臘人攻克特洛伊後，回程只花了4天 的時間。貝利薩留的旗艦引導著整個艦隊的行進路線，白天張著醒目的紅色船帆，夜間在船首點起耀眼的巨大火炬。他們不停地在島嶼之間航行，到了瑪利亞和提納烏姆 的海岬就準備轉向。舵手的責任是要使為數眾多的船隻保持正確的隊形和適當的間隔，風向很順而且風力適度，他們的苦心沒有白費，最後安全抵達了梅塞尼亞海岸。部隊在梅索尼下船，充分休息以恢複海上航行的疲勞。就在這個地點，勇敢的士兵獻身為公眾服務，卻體驗到貪婪是如何藐視數以千計人員的生命，這種貪婪是伴隨著職權而產生的。按照軍中勤務的規定，野戰爐灶要為羅馬人每天供應兩次麵包或餅乾，因為重量的損失，容許減少四分之一的定額配給。為了獲得少許可憐的利潤，以及節省木柴的費用，卡帕多細亞的約翰身為統領竟然下達命令，麵粉要先在君士坦丁堡用浴場燒水的火稍為烘焙一下，等到裝糧食的麻袋打開，將潮濕而發霉的麵糰發給部隊。這種腐敗又不衛生的食物，因為炎熱的天候和季節更加嚴重，立即產生了流行的傳染性疾病，導致500名士兵喪生。還是貝利薩留採取防範措施，才得以恢複大家的健康。他在梅索尼供應新鮮的麵包，同時毫不顧慮會得罪在朝的大臣，基於正義和人道表達自己的氣憤之情。皇帝聽到他的抱怨以後，對將領的處置表示嘉許，但是並沒有處分大臣。
離開梅索尼港口，舵手沿著伯羅奔尼撒的西岸航行，直抵扎辛瑟斯或稱扎特島，從起航到越過愛奧尼亞海的航程是100里格 （在他們的眼裡，這是最困難的一段海域）。現在艦隊遭到未曾意料之事，在無風狀況下浪費了16天的時間緩慢航行。要不是機靈的安東妮娜保存了一瓶水，埋在船上一個沙堆的深處，可以避免陽光的照射，甚至連將領本人都要飽嘗口渴的痛苦。最後他們在西西里南部的考卡納港 ，找到安全而友善的庇護所。哥特官員以狄奧多里克的女兒和外孫的名義，統治這個島嶼，所以會服從極不平常的命令，把查士丁尼的部隊視為友人和同盟，充分供應所需的糧食，為騎兵隊配發缺少的馬匹。普羅科皮烏斯很快從敘拉古趕回來，獲得了汪達爾人當前狀況和企圖的正確資料。他所提供的情報使貝利薩留下達決心，要立即展開行動。這種迫不及待的明智作為，適時獲得風向的幫助。艦隊離開西西里的視線，駛過馬爾他島後，發現了阿非利加的海角，在強烈的東北風吹襲下沿著海岸航行，最後在卡普特·瓦達海岬所圍成的海灣中下錨，迦太基在南邊大約5天的行程。
要是傑利默知道敵軍正在接近，就會延緩對撒丁尼亞的征服行動，集中兵力防衛他本人和王國的安全。這支特遣部隊有5000名士兵和120艘戰船，將會回來加入汪達爾人的留守部隊。根西里克的後裔可以用水師奇襲來壓制敵軍的艦隊，因為那些塞滿貨物的運輸船無法從事作戰行動，輕型雙桅帆船參加海戰似乎只有逃跑的資格。貝利薩留在航行途中無意間聽到了士兵的談話，使他內心驚慌不已。這些人都感到憂慮而要相互壯膽，強調只要能登陸上岸，就願意用武器來維護自己的榮譽，如果在海上受到攻擊，只有毫不羞愧地認輸，他們沒有勇氣同時與風浪和蠻族搏鬥。 明了大家的想法以後，貝利薩留決定只要抓住一線機會，就趕快率領部隊登上阿非利加的海岸。在作戰會議中，他保持審慎和明智的決定，反對大家非常魯莽的建議，那就是用艦隊搭載兵力直接駛往迦太基的港口。離開君士坦丁堡3個月以後，人員、馬匹、武器和軍需物資全部安全登陸，每艘船留下5名士兵在甲板上擔任警衛，整個艦隊布置成半圓形。登陸的部隊在海岸附近佔領營地，按照古老的軍事教範，用防壁和塹壕加強防備的力量。他們發現了一處清澈的水源，可以解除口渴的煎熬，使羅馬人堅信得到了上帝的保佑。次日早晨，鄰近地區有幾處田莊遭到搶劫，貝利薩留懲罰了違犯法紀人員，在最關鍵的時刻掌握這個稍縱即逝的機會，諄諄教誨全軍要奉行公正、節制和真誠的政策原則。將領說道：
當我開始接受征服阿非利加這個任務的時候，成功不是靠著部隊的數量和作戰的勇氣，而是當地人士的友情和對汪達爾人勢不兩立的痛恨。要是你們要毫不在意地用掠奪的方式來獲得那些只花少許金錢就可買到的物品，就等於是剝奪我僅有的希望。要知道暴力行為會使他們之間的世仇和解，聯合起來成為公平和神聖的同盟，對抗侵略他們國家的敵軍。
將領的訓示通過嚴格的軍紀要求來貫徹執行，士兵本身立刻感受到有益措施所產生的效果，表示出由衷的欽佩。居民無須拋棄家園或是隱匿財物，用收費公平和貨物充足的市場供應羅馬人的所需，行省的文職官員以查士丁尼的名義繼續行使原有的職責，教士基於本能和利益的動機，盡心儘力為信仰正統教義的皇帝奮鬥不息。離營地一日行程的一個名叫蘇勒克特的小鎮 ，獲得第一個開城簞食壺漿以迎王師的榮譽，與羅馬人重建古老的隸屬關係；利普提斯和阿德魯梅圖姆這些大城，在貝利薩留出現時，也都效法蘇勒科特歸順的榜樣。他在毫無抵抗之下到達格拉西，汪達爾國王在此建造了一座宮殿，距離迦太基有50英里。到處是濃蔭的樹叢、冷冽的流泉和美味的水果，讓疲睏的羅馬人盡情休息恢複體力。普羅科皮烏斯認為此地的果園真是前所未見，無論在東方還是西方都難以比擬，這可能是歷史學家喜愛美食或者是太過勞累所致。汪達爾人經過三代的時間，優裕的生活和溫暖的氣候使得他們刻苦耐勞的習性喪失得一乾二淨，不知不覺中成為奢侈頹唐的種族。他們的田莊和花園就波斯人看來真是「天堂」 ，讓人能夠享受涼爽而安寧的休憩，每天在沐浴一番之後，蠻族的餐桌上擺滿山珍海味。他們穿著絲質長袍，模仿梅德人的形式，非常寬大飄逸，用金線綉出各種圖案和花樣。在他們的生活中要勞動出力的工作，就只有談情說愛和騎馬出獵，空閑的時光充滿各種消遣，像是啞劇、賽車以及劇院的歌舞表演。