Johannes Østensjø a créé officiellement sa compagnie, Østensjø Rederi en 1974 à Haugesund en Norvège. Un bureau à Aberdeen, en Ecosse, était également ouvert à ce moment-là. Auparavant en 1973, un premier accord pour la construction de quatre navires ravitailleurs de plates-formes était signé avec un chantier naval en Afrique du Sud. Østensjø a été le premier au monde, en 1975,  à surélever les parois des plages arrières de ses PSV (Platform Supply Vessel) pour assurer la sécurité des marins travaillant sur le pont. Il sera aussi le premier à installer le positionnement dynamique (DP) sur un supply, le "Edda Fjord" en 1982.
Østensjø signera des contrats de remorquage et de ravitaillement de plates-formes avec les plus grands groupes pétroliers offshore tout au long de ces années. En 2001, il recevait le remorqueur d'escorte "Ajax", alors le plus grand et le plus puissant du genre au monde lors de sa livraison. De nombreuses innovations jalonnent le parcours de la compagnie. Østensjø a une filiale, Edda Accomodation qui commandait en 2008 un navire d'assistance capable de loger 600 spécialistes de l'offshore, dont 300 en cabine simple. Ce "flottel" portera une passerelle télescopique capable de se connecter hydrauliquement à toute construction offshore. Le "Edda Fides" entrait en service en 2011.
En 2015, Østensjø entrait dans le segment de l'éolien offshore renouvelable avec la mise en service d'un navire sous contrat pour le groupe énergétique danois Ørsted. En 2017, la compagnie prenait livraison de ses premiers navires, trois remorqueurs d'escorte de 160 t, fonctionnant au GNL. En 2018, Østensjø recevait deux Support Offshore Vessel (SOV), les "Edda Passat" et "Edda Mistral" qui travailleront toujours pour Ørsted sur ses parcs éoliens.
En juillet 2022, deux des navires d' Østenjø, les "Edda Ferd" et "Edda Sun" participaient à un des projets environnementaux les plus ambitieux de Norvège: le rapatriement des infrastructures (ateliers et centrale électrique) de la mine de Svea Nord, sur l'île de Svlabard.  Cette mine retourne à l'état sauvage après cent ans d'exploitation. Les deux navires assuraient les transports vers le port de Longyearbyen, pour ce projet de grande envergure.
La coentreprise USV, du trio norvégien composé de Solstad, Ostenjo et DeepOcean passait commande en juillet 2023 auprès du chantier naval espagnol Gondan de leur premier navire autonome destiné à l'éolien offshore. Long de 24 mètres pour 7,5 mètres de large, le navire pourra rester 30 jours en opération sans refaire le plein ou recharger. Il sera équipé d'un ROV de travail capable d'atteindre 1500 mètres de profondeurs. Il sera opéré à distance depuis le rivage pour ses opérations d'inspection et de travaux sous-marins. Le navire pourra intervenir dans des conditions de mer difficiles, il devrait entrer en service en 2025.