Het initiatief voor de onderneming iswerd genomen door de uit [[Winterswijk (plaats)|Winterswijk]] afkomstige textiel-industrieel en tevens Tweede Kamerlid [[Jan Willink]], bijgenaamd Spoor-Jan. Hij had eerder de [[Nederlandsch Westfaalsche Spoorweg-Maatschappij]] (NWS) en de [[Geldersch-Overijsselsche Lokaalspoorweg-Maatschappij]] (GOLS) opgericht. De NOLS was in zijn plannen een noodzakelijke schakel voor een railverbinding vanaf de Duitse grens bij Winterswijk tot aan de [[Noordzee]]. De zeehaven [[Harlingen (stad)|Harlingen]] had zijn voorkeur. Maar uiteindelijk was hij ook tevreden met een verbinding naar [[Delfzijl]]. In 1888 dient hij een aanvraag voor een concessie in en in 1890 krijgt hij de ontwerpconcessie. In de aanvraag was voorzien in een lijn van [[Neede]] naar [[Ommen]], waardoor het NOLS net zou aansluiten op het net van de reeds bestaande GOLS-lijnen in [[Twente]] en de [[Achterhoek]]. Deze belangrijke verbinding tussen de NOLS- en de GOLS-lijnen is er evenwel nooit gekomen. Wel is later door de [[Locaalspoorweg-Maatschappij Neede-Hellendoorn]] de [[Spoorlijn Neede - Hellendoorn]] aangelegd.
Daarna verlooptverliep het verder ontwikkelen van de spoorlijn moeizaam, onder andere door meningsverschillen met de regering. De plannen ondergaan diverse wijzigingen. In 1896 overlijdtoverleed Jan Willink, enwaarna zijn zoon A. Willink neemt het initiatief overovernam. [[Cornelis Lely|Minister Lely]] loodstloodste in 1898 de wet voor de NOLS door het parlement.
De maatschappij werd in 1899 opgericht. De onderneming krijgtkreeg [[Zwolle (Overijssel)|Zwolle]] als vestigingsplaats. In datzelfde jaar krijgtkreeg de maatschappij de definitieve concessie en wordtwerd er een contract gesloten met de [[Maatschappij tot Exploitatie van Staatsspoorwegen|Staatsspoorwegen]] voor de exploitatie van lijn. Voor het ontwerpen van de gebouwen van de NOLS, zoals stations en haltegebouwen, neemtnam de maatschappij de architect [[Eduard Cuypers (architect)|Eduard Cuypers]], een neef van [[P.J.H. Cuypers]], in de arm. Eduard Cuypers had eerder ook het stationsgebouw van [[Station 's-Hertogenbosch|'s-Hertogenbosch]] gebouwd. [[Standaardstations van de Noordoosterlocaalspoorweg-Maatschappij|De stations worden geclassificeerd]] en elke klasse krijgtkreeg een vast basisontwerp, waarbinnen wel gevarieerd wordtwerd.
