Kada je Tvrtko I Kotromanić 1353. godine došao na vlast Venecija, koja mu je bila susjed u Dalmaciji, se držala sasvim sigurno. Zahvalni zbog potpore Ugarske, Tvrtko i njegova majka su pravili ustupke ugarskom kralju, zanemarujući mletačke interese u Dalmaciji. Uskoro se stanje počelo pomjerati na mletačku štetu. U teškim sukobima sa Ugarima od 1356. do 1358. godine, Venecija je računala na nekadašnju uspješnu saradnju sa Bosnom, koju je namjeravala obnoviti i sa novim bosanskim vladarom Tvrtkom na sve moguće načine.
Ipak, nakon što je Zadarskim mirom iz 1358. godine privremeno odstranjena iz Dalmacije, Venecija je ponovo izgubila interes za saradnju sa Bosnom. Tako je sve bilo dok Tvrtko nije dokazao svijetu da je samostalan i moćan vladar, nakon što je 1363. godine teško porazio ugarsku vojsku koja je namjeravala pokoriti Bosnu. Tvrtko je nastojao iskoristiti takvu situaciju te 29. marta 1366. godine izdaje “sicut promissimus” kojim potvrđuje da će štiti sva mletačka prava u svakom mjestu koje je pod njegovom kontrolom.
U dokumentu je sebe i svoju majku potpisao kao “srdačne mletačke prijatelje”. Ipak, sve do 1378. godine i izbijanja rata između Venecije i Genove, nemamo pouzdanih podataka šta se dešavalo između Bosne i Venecije. Obzirom da je Ugarska stala na stranu Genove, Venecija je nastojala uspostaviti prisne veze sa Bosnom. Svakako da je jedan od razloga tome i Tvrtkovo krunisanje za kralja 1377. godine, poslije čega je postao najznačajniji balkanski vladar. Da bi izgradio luku u Kotorskom zaljevu, na mjestu današnjeg Herceg Novog, koja mu je bila vidno neophoda da smanji izvozno – uvoznu zavisnost Dubrovnika, Tvrtko nastoji da se otvorenije osloni na Veneciju koja je 1382. godine, našla način da mu se oduži za podršku u ratu.
Smrću ugarskog kralja Ludvika, brojni su osjetili olakšanje. Novim stanjem se želio okoristiti svako pa i sam Tvrtko. Hrvatski ban je 20. septembra 1382. godine, bojeći se pritiska sa bosanske strane, tražio od Trogira da o svom trošku opremi osam borbenih rodova koji će čuvati gradove uz bosansku granicu. Od moguće bosanske akcije strepili su i Dubrovčani pa su već 22. oktobra 1382. godine odluči da sa Zadrom i ostalim saveznicima sklope savez “protiv Venecije i svih njezinih kopnenih saveznika”, misleći time i na kralja Tvrtka. Time je raspoloženje za Tvrtka poraslo i u Veneciji. Štaviše, više se nisu plašili niti mogućnosti da bosanska flota zaplovi Jadranom.
Kada je on, početkom 1383. godine, ponovo nastojao da formira bosansku flotu, uz dogovor sa Mlečanima, za prvog admirala srednjovjekovne bosanske flote je postavljen patricij Nikola Beseja. Imenovanje je i u mletačkim krugovima uzimano kao gest povjerenja prema izabranom kao i prema mletačkoj vlasti – “gest koji može očuvati i uvećati prijateljstvo dviju strana”. Tvrtko je odmah ovlastio Baseja da u Veneciji nabavi jednu lahku galiju sa opremom, koja mu je već 27. marta 1383. godine odobrena, kao što mu je i 5. maja 1383. godine odobreno da u mletačkom brodogradilištu, na svoj trošak, izgradi i opremi još dvije galije. Zanimljivo je da je Tvrtku u tom vremenu odobreno sve što je tražio od Venecije. Ohrabren time, zatražio je i da ga, sa sinovima i nasljednicima, Veliko vijeće uvrsti među mletačke građane, što je 27. jula 1383. godine i prihvaćeno.
Novo mletačko – bosansko zbližavanje praćeno je i saradnjom na izgradnji bosanske flote, prve i jedine koju je Bosna imala u svojoj historiji. Ovakvo stanje vidno je zabrinulo Ugarsku koja je preko svoje kraljice nastojala ubijediti Veneciju da spriječi izgradnju i opremanje bosanskih galija, te zatražila garanciju da one neće djelovati protiv ugarskih zemalja i podanika. Venecija je Ugarsku umirivala time što ih je uvjeravala da galije neće biti naoružane i da je za admirala imenovan mletački nobil, kome će biti naređeno da na ugarske zemlje gleda prijateljski i ne nanosi im bilo kakvu štetu. Tvrtko nije želio dvojnu ulogu svoga prvog admirala, tako da je on u drugoj polovini 1384. godien razrješen obaveze.
Baseja je bio pod pritiskom iz same Venecije zbog njezinog zakona iz 1356. godine po kojem mletački građani ne smiju prihvatiti rekotorske poslove u zemljama koje nisu podložne Veneciji. Samim time pokrenuto je i pitanje da li je i Baseja time obuhvaćen. Kada je 24. avgusta 1384. godine o tome odlučivalo Veliko vijeće, prvo se glasalo o stajalištu da ograničenje ne pogađa Baseja i da može obavljati povjerenu dužnost prvog bosanskog admirala, što je podržalo 279 vijećnika. Za suprotno stajalište glasalo je 385 vijećnika, dakle većina.
Do kraja godine je između Tvrtka i Venecije razmijenjeno više pisama o slučaju Nikole Baseja jer mu je kralj dugovao znatnu sumu novca za poslove poduzimane u njegovo ime. Tako je Baseja stvorio novčane obaveze prema mnogim osobama koje su tražile naplatu, a on se nije usuđivao pojaviti se, kako ne bi bio uhvaćen za tuđe dugove. Tvrtko je pisao da će dugovi biti riješeni, ali se Baseja nije usuđivao izaći u javnost. Pritisak je počela vršiti i Venecija, kako bi i Baseja mogao izvršiti svoja dužnićka plaćanja prema državi (porezi). Tek poslije toga, kralj je 2. aprila 1385. godine, obećao da će uskoro doći njegovi izaslanici i potpuno izmiriti obaveze.
Pošto se to nije desilo ni za dva mjeseca, kralj je opomenut da će se Venecija u konačnici sama postarati oko okončanja spora. Zbog ovakvog stanja usporena je i izgradnja prve bosanske flote, što Tvrtku nije odgovarao pa su bosanski izaslanici konačno stigli i izmirili dugove. Nakon toga 23. novembra 1385. godine Venecija je odobrila da Tvrtko može bez ikakvih prepreka preuzeti svoje galije sa svom potrebnom opremom. Time je Kraljevina Bosna i zvanično dobila svoje prve brodove.
