Mezi hvězdami putující kapitula ctnostné pověsti, vlastní dějiny Potulných Mariňáků je popisují jako jednu z kapitul 23. zakládání Adeptus Astartes, které dle mnohých pramenů proběhlo v pozdnějších letech 37. milénia. 23. zakládání je obecně mnoha učenci považováno za jedno z řady propojených zakládání z této doby, jejichž účelem bylo obnovit sílu a dosah sil vesmírných mariňáků Impéria, kteří v uplynulých tisíciletích utrpěli velké ztráty. Dle Requiem Malesent svatého Kybry bylo během tohoto období ne méně než padesát sedm kapitul vesmírných mariňáků zničeno přímo, stalo se renegáty či bylo prohlášeno za ztracené. Bylo to období, které pronásledovaly takové pohromy jako Věk rozkolu, katastrofální Prokleté zakládání, útoky sil Chaosu a řádění orků podél nehlídaných hranic Impéria.
Potulní Mariňáci, spolu s několika dalšími kapitulami, byli od počátku zamýšleni jako kapitula, které stráví svou existenci na nekončnící kruzádě a které budou vytvořeny z těch nejstabilnějších zásob genoštěpu dostupných Adeptus Mechanicus. Texty sepsané v té době a od té doby uctívané, které jsou uchovávány v archivech Potulných Mariňáků na Vilamu, předurčují kapitulu k tomu, aby byla "provždy v hledání a boji, neznajíc jiného domova než krásu Císařova slitování, nacházejíc smysl jen v ničení nepřátel lidstva." Od svého počátku Potulní Mariňáci věrně následovali tento směr, bez odpočinku cestujíce mezi válečnými zónami mezi vzdálenými, rozptýlenými hvězdami Impéria, a jsou jednou z mála kapitul, o kterých je známo, že se kdy vydaly na tažení daleko za okraj lidských domén a vrátily se.
Další podrobnosti o původu kapituly lze nalézt v Mythos Angelica Mortis, velkolepém díle zabývajícím se vesmírnými mariňáky té doby, které popisuje pět nově založených kapitul a jejich pokrevních předků - s Potulnými Mariňáky a Orlími Válečníky jako jejich přímými předchůdci. Genoštěp Orlích Válečníků pochází z linie Ultramariňáků, ačkoli důvod, proč byli Orlí Válečníci sami vybráni pro takovou čest, že je "pojmenované" zakládání vybíráno z jejich řad, zůstává pro budoucí pokolení ztraceno.
Potulní Mariňáci si pro sebe vydobyli řadu slavných bitevních skutků tím, že ve jménu Císaře podstupovali jednu křížovou výpravu za druhou, z nichž některé stále žhnou na stranách historie kapituly, zatímco jiné už byly dávno zapomenuty. Kapitula se také zřetelně účastnila četných válek, které dohromady tvořily Věk vykoupení, ve které byla Imperiální víra znovu upevněna v neovladatelném Impériu očištěném v krvi odpadlíka. Nicméně, Potulní Mariňáci jsou známi zejména pro své pozdější křížové výpravy do vnější temnoty galaxie.
Od samotného počátku bylo úmyslem Potulných Mariňáků účastnit se nekončících křížových výprav, očisťovat kosmos od jakékoli špíny, jež by mohla urazit Císaře či bránit lidské nadvládě nad hvězdami. Kvůli tomu upravila kapitula své organizační schéma okolo představy samostatné stability každé z jejích kompanií. Během své existence kapitula Potulných Mariňáků nikdy neurčila formální klášterní pevnost ani přesný domovský svět. Namísto toho zná kapitula jen málo odpočinku, neboť její členové neustále cestují, aby rozšířili hranice Impéria. Byť toto omezuje sounáležitost mezi vesmírnými mariňáky přiřazenými k různým kompaniím, tato dodatečná taktická flexibilita jim vždy velmi dobře sloužila v plnění jejich předurčené role.
Věk vykoupení, který trval po většinu 37. tisíciletí, byl obdobím, ve kterém Imperiální kult poprvé získal své současné rozměry autority v Impériu. Ve stoletích vedoucích k této době začala být Ecclesiarchie zkorumpovanou. Nakonec byla tato korupce odhalena a přemožena. Se změnou vedení se stala víra v Boha-Císaře zásadní součástí imperiálního života. Mnozí z těch, kteří přijímali víru vším svým zanícením, cítili, že trest za strašlivé zločiny, které se udály v minulých stoletích, je nezbytný. Pro jiné byla jedinou představitelnou službou představa vydání se křížovou výpravu proti cizákům a silám heretiků, kteří zamořovali galaxii.
Skrze první století od svého vytvoření se Potulní Mariňáci stali produktem své éry. Jejich bitevní bratři se účastnili nespočtu křížových výprav, od těch zahrnujících pár světů ve hvězdném systému po ohromné války, které se táhly celými subsektory. Během účastí v těchto nespočetných tažením za odčinění předchozích hříchů Impéria kapitula prokázala svou hodnotu jako strážci a váleční ambasadosři v místech, na která se lidstvo ještě neodvážilo.
Během let 390.M38 až 443.M38 kapitula Potulných Mariňáků uzavřela spojenectví s domem svobodných obchodníků Ecalu. Důvod pro tuto dohodu zůstává střeženým tajemstvím obou stran. Nicméně zůstává zřejmým, že vazby vytvořené v té doby zůstávají na svém místě i v dnešních dnech. A do tohoto dne bitevní bratři Potulných Mariňáků nadále slouží v detašované pozici na plavidlech domu Ecale. Může tomu tak být, že úkol, ke kterému se upsali, prostě ještě nebyl splněn. Může tomu ale být i tak, že kapitula má vůči tomuto rodu nějaký dluh, který nelze jen tak rychle splatit. Tato služba pro dům Ecale je mezi členy kapituly považována poctu. Ti, kteří takto sloužili, nosí znak tohoto domu svobodných obchodníků i dávno poté, co se vrátí ke kapitule. Mnozí taktéž nosí velmi zdobené silové zbroje či výzbroj, které obdrželi jakožto dar od tohoto domu.
Na počátku 40. milénia pět kompanií Potulných Mariňáků vytvořilo vojenské jádro Kadyronské výpravy do Hazerothské hlubiny v sektoru Calixis. Tato expedice, vedená lordem inkvizitorem Kadyronem, je považována za naprostý neúspěch. Jen jediná bitevní bárka přežila tuto expedici. Během výpravy kapitula ztratila většinu Land Raiderů, Dreadnoughtů a řadu plavidel schopných cesty warpem, stejně jako nespočet bitevních bratří. Kdyby nebylo jejich systematického ukládání genoštěpu, kapitula by se možná ze ztrát nikdy nevzpamatovala. Dokonce i se zrychlením přijímání noviců, kapitula Potulných Mariňáků budu pravděpodobně strádat ze ztráty nenahraditelného vybavení i v následujících tisíciletích.
Kapitula se nedávno účastnila Corinthské křížové výpravy proti silám Skargorova Waaagh! v systému Corinth. Pod vedením Marneuse Calgara z Ultramariňáků křížová výprava rozdrtila orkskou říši a prakticky eliminovala cizáckou hrozbu v tomto regionu na celá desetiletí. V průběhu války 4., 6. a 9. kompanie získaly obrovské uznání pro osvobození ultramariňácké 3. kompanie, když ta byla prakticky přiražena k zemi mnohem mocnější orčí flotilou. Bitevní bratři Potulných Mariňáků se vydali do naloďovacích akcí proti tuctům Skargorových lodí typu Terror, poskytujíce tak Ultramariňákům podporu potřebnou k obrácení vývoje bitvy ve prospěch Císařovy vůle. Marneus Calgar došel až tak daleko, že udělil kapitule jednu z posvátných relikvijních čepelí Ultramariňáků jako znak jejich pospolitosti.
Významné kampaně
Corintská křížová výprava (698.M41) - kapitula Potulných Mariňáků slouží jako součást kombinované expediční síly vesmírných mariňáků složené z Ultramariňáků, Andělů Rozhřešení, Truchlících, Stříbrných Lebek, Císařových Kos, a padesáti regimentů imperiální gardy vedených kapitulním pánem Ultramariňáků Marneusem Calgarem, která byla vyslána proti orkům Charodonu. Během hrdinné sedm let dlouhé křížové výpravy tyto imperiální síly způsobily sérii velkých porážek rostoucí hrozbě Skargorova Waaagh!. Orkové byli rozdrceni a jejich hrozba zmizela na víc než třicet standardních let.
Badabská válka (901-908.M41) - Do Badabské války byli Potulní Mariňáci povoláni z Východního okraje nejvyššími lordy Terry v roce 904.M41, aby posílili řady kapituly Ohnivých Jestřábů. Brzy však zjistili, že jsou plně zaměstnáni ochranou imperiálních obchodních tranzitních lodí, což byl úkol, který zastarávali po zbytek konfliktu.
Pád Vilamusu (999.M41) - V roce 999.M41 Huron Temné srdce ze zrádcovských Rudých Korzárů spolu s bandou Nočních Lordů vedenou šampiónem Chaosu zvaným Uchvácený zosnuje plán na ukradení velkého množství genoštěpu Astartes pro vytvoření nových vesmírných mariňáků Chaosu, kteří by doplnili renegátské řady, které byly ztenčeny během Badabské války. Kapitulní klášterní pevnost Potulných Mariňáků Vilamus, vytvořená na flotile založenou kapitulou jako bezpečná základna pro její repozitář genoštěpu, byla vybrána kvůli relativně malé velikosti posádky. Odlákávajíce většinu kapituly pryč ze světa, podařilo se Rudým Korzárům vyřadit z fungování pevnostní nulitní štíty a zahájit přesně zaměřený útok, který zneutralizoval energetickou síť klášterní pevnosti a její automatické obrany. Následný útok vedl ke ztrátě takřka veškeré vzácné zásoby generitického materiálu kapituly, odsuzující jí k dlouhému, pomalému úpadku, jestliže se nepodaří genoštěp znovu získat. Naneštěstí, Noční Lordi a Rudí Korzáři se brzy vrhli jeden na druhého, když se Noční Lordi pokusili získat jeden z útočných křižníků, Echo Zatracení, a získat tak veškerý získaný genoštěp.
