The Brainerd and Northern Minnesota Railway was originally rooted in the Gull Lake and Northern Railway, which had already constructed a small line west of Brainerd in 1889. The GL&N itself was nothing more than a narrow gauge logging line taking advantage of the regions natural lumber, and which had additionally started grading a line north out of Brainerd by 1892, the year that the B&NM was chartered and absorbed the GL&N. The B&NM, with a grander vision of eventually reaching the border with Canada, started building its line using the existing GL&N grading out of Brainerd to the vast pine forests to the north.
The original route first reached Munroe and then ended at Spider Lake. This line, like the original GL&M, was a narrow gauge route. Early on, the B&NM saw the operational need to exchange with other nearby railroads, which were of standard gauge track, so it converted its line to standard gauge in 1893, after only one year in operation. However, with the financial panic of 1893, along with construction and maintenance costs within the rugged terrain around Spider Lake, the B&NM decided in 1894 to abandon the portion of its line between Lake Hubert to Spider Lake, a distance of 30 miles, and instead surveyed and constructed a new line from Lake Hubert to Leech Lake, completed later that year. Construction continued northward from there, reaching Walker in 1896, and eventually reaching Bemidji in December of 1898. All told, the B&NM had built 92 miles of mainline track between Brainerd and Bemidji, not including various logging spurs and branches it had built along the way.
In 1900, the B&NM, widely considered the most important logging railroad in the state of Minnesota at the time, was merged into the Minnesota & International Railway, a conglomeration of logging railroads in the region. With financial interested vested in the M&I by Northern Pacific Railroad, the M&I to continue building from Bemidji northwards, ultimately reaching International Falls, MN, on the border with Canada, by 1907.
The original B&NM line between Brainerd and Bemidji, now under M&I ownership, was transferred to the NP upon its outright purchase of the M&I in 1941. From there, the NP merged with other railroads to form the Burlington Northern Railroad in 1970.
By the 1980s, with only a scant number of shippers along the line requiring infrequent service, and mounting deferred track maintenance, BN opted to abandon the B&NM. The last train ran along the line on August 15, 1985, and the line was formally abandoned soon after.
Today, the former right-of-way serves as the Paul Bunyan State Rail Trail.