Schon bei der Gründung der NBDS mangelte es ihr an Geld. Es fanden sich in Holland und Deutschland nicht genügend Zeichner für das Grundkapital der Gesellschaft. Hinzu kamen ein unzuverlässiger Bauunternehmer und Kreditkündigungen der Banken. Auch ein Gründer der Gesellschaft, ein Rotterdamer Notar, verließ einen Tag vor der Betriebseröffnung am 15. Juli 1873 das vermeintlich sinkende Schiff. Schließlich ließ die SS, die große Staatsbahngesellschaft, den Eröffnungszug nicht in den Bahnhof Boxtel einfahren. In Deutschland zeigte sich die große Köln-Mindner Bahn, an die die NBDS in Wesel anschloss, recht unzufrieden mit den geringen Frachtmengen, die ihr von der NBDS übergeben wurden.

In ihrem Behauptungskampf gegen die übermächtige SS erfand die NBDS den gebrochenen Transport von Massengütern (deutsche Kohle und Ölsaat aus Übersee zur Margarineherstellung) von eigenen Binnenschiffen auf ihre Waggons im eigenen Kanalhafen in Veghel. Zur Strafe entzog man der NBDS in Holland für 4 Jahre den lukrativen Schnellzugverkehr von und nach Berlin, obwohl durch den Umweg über Venlo und Krefeld/Duisburg häufig Verspätungen eintraten und Reisende ihre Anschlusszüge nach Berlin verpassten. Ferner erhielt sie nicht die staatliche Genehmigung zur Verlängerung ihrer Strecke über Boxtel hinaus nach Belgien. Auf den Anschlussstrecken der Preußischen Staatseisenbahn durfte die NBDS jedoch die großen Schnellzüge über Wesel hinaus nach Haltern, Münster, Oberhausen oder Essen mit eigenen Maschinen und eigenem Personal fahren.

Verladekran im NBDS eigenen Kanalhafen in Veghel

Erst als die englische Great-Eastern Railway mit ihren eigenen Schiffen den Fährverkehr zwischen Harwich und Hoek van Holland mit Anschluss an die holländische Konkurrenzbahn Hollandsche Spoorweg Mp. (HSM) aufnahm, begann 1892 eine reibungslose Zusammenarbeit aller an der Vlissinger Postlinie beteiligten Bahngesellschaften. Die NBDS wurde dabei mit ihrer Strecke zu einem wichtigen und anerkannten Glied in der internationalen Bahnverbindung London - St.Petersburg.

Zeitweise besserte sich dadurch die ansonsten schwierige finanzielle Situation der Gesellschaft in den Jahren bis zum 1. Weltkrieg. Der wachsende Zugverkehr, vor allem bei den internationalen Schnellzügen, zwang sogar dazu, den Streckenteil von Boxtel bis Goch von 1903 bis 1912 zweigleisig auszubauen.